By Ignacio M. Pelayo

ISBN-10: 146148698X

ISBN-13: 9781461486985

ISBN-10: 1461486998

ISBN-13: 9781461486992

​​​​​​​​Geodesic Convexity in Graphs is dedicated to the examine of the geodesic convexity on finite, uncomplicated, hooked up graphs. the 1st bankruptcy contains the most definitions and effects on graph idea, metric graph concept and graph course convexities. the next chapters concentration completely at the geodesic convexity, together with motivation and heritage, particular definitions, dialogue and examples, effects, proofs, routines and open difficulties. the most and such a lot st​udied parameters regarding geodesic convexity in graphs are either the geodetic and the hull quantity that are outlined because the cardinality of minimal geodetic and hull set, respectively. this article experiences a variety of effects, bought over the last one and a part decade, pertaining to those invariants and a few others akin to convexity quantity, Steiner quantity, geodetic generation quantity, Helly quantity, and Caratheodory quantity to a variety a contexts, together with items, boundary-type vertex units, and excellent graph households. This monograph can function a complement to a half-semester graduate direction in geodesic convexity yet is basically a advisor for postgraduates and researchers drawn to subject matters concerning metric graph idea and graph convexity concept. ​

Show description

Read or Download Geodesic Convexity in Graphs PDF

Best graph theory books

Graphs and Networks: Transfinite and Nonstandard by Armen H. Zemanian PDF

This self-contained e-book examines effects on transfinite graphs and networks completed via a continuous examine attempt in past times numerous years. those new effects, protecting the mathematical conception of electric circuits, are various from these offered in formerly released books through the writer, Transfiniteness for Graphs, electric Networks, and Random Walks and Pristine Transfinite Graphs and Permissive electric Networks.

Download e-book for kindle: Algorithmic Graph Theory and Perfect Graphs by Martin Charles Golumbic

Algorithmic Graph thought and ideal Graphs, first released in 1980, has develop into the vintage creation to the sector. This new Annals variation keeps to show the message that intersection graph types are an important and critical instrument for fixing real-world difficulties. It is still a stepping stone from which the reader may well embark on one of the interesting study trails.

An Introduction to Catalan Numbers by Steven Roman PDF

This textbook presents an creation to the Catalan numbers and their extraordinary houses, in addition to their a variety of functions in combinatorics. Intended to be obtainable to scholars new to the topic, the ebook starts off with extra trouble-free themes prior to progressing to extra mathematically refined subject matters.

Additional info for Geodesic Convexity in Graphs

Example text

Take integers a, b ≥ 2. We distinguish cases. Case 1: c = a + b. Consider the graph G1 shown in Fig. 17. Check that {x, y, y2 , . . , y3s−1 } and {y3s , x1 , . . , xr } are a minimum dominating set and a minimum geodetic set of G, respectively. Notice also that the union of these two sets produces a minimum geodetic dominating set. Hence, taking r = b − 1 and s = a − 2, we obtain the desired values. Case 2: a = b = c. Consider the graph G2 ∼ = Ka K1 shown in Fig. 17. Check that {yi }a i = 1 is a minimum geodetic dominating set.

Xs } is both a minimum geodetic set and a minimum geodetic dominating set. Hence, taking r = a − 1 and s = b − a + 1, we obtain the desired values. Case 4: b < a = c. Consider the graph G4 shown in Fig. 17. Check that {z1 , . . , zr , x0 , x3 , . . , x3s } is both a minimum dominating set and a minimum geodetic dominating set and that {z1 , . . , zr , x3s } is a minimum geodetic set. Hence, taking r = b − 1 and s = a − b, we obtain the desired values. Case 5: max{a, b} < c < a + b. Consider the graph G5 shown in Fig.

If 3 ≤ k ≤ 4, P4 and P5 . Suppose thus that k ≥ 5. Take two copies G1 and G2 of K2,n−k and a copy G3 of P2k−n−2. Let G be the graph obtained from G1 , G2 , and G3 by identifying the vertices w1 and w2k−n−2 with y1 2k−n−2 and x2 , respectively, where V (Gi ) = {xi , yi } ∪ {zi j }n−k j=1 and V (G3 ) = {wi }i=1 (in Fig. 10a the case n = 14 and k = 10 is shown). Notice (1) G is a K3 -graph of order n, (2) 2k − n − 2 ≥ 0, and (3) if n = k + 1, then G is Pn . We form convex sets of orders 1 through 2k − n − 2 by taking a subpath of appropriate length from G3 .

Download PDF sample

Geodesic Convexity in Graphs by Ignacio M. Pelayo

by Ronald

Rated 4.18 of 5 – based on 28 votes