Graph Theory

Geodesic Convexity in Graphs by Ignacio M. Pelayo

By Ignacio M. Pelayo

​​​​​​​​Geodesic Convexity in Graphs is dedicated to the research of the geodesic convexity on finite, easy, attached graphs. the 1st bankruptcy contains the most definitions and effects on graph concept, metric graph thought and graph course convexities. the subsequent chapters concentration completely at the geodesic convexity, together with motivation and history, particular definitions, dialogue and examples, effects, proofs, routines and open difficulties. the most and so much st​udied parameters related to 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 quite a few effects, received over the past one and a part decade, touching on those invariants and a few others comparable 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 ideal graph households. This monograph can function a complement to a half-semester graduate direction in geodesic convexity yet is essentially a advisor for postgraduates and researchers attracted to themes on the topic of metric graph thought and graph convexity conception. ​

Show description

Read Online or Download Geodesic Convexity in Graphs PDF

Similar graph theory books

Distributed Algorithms (The Morgan Kaufmann Series in Data Management Systems)

In allotted Algorithms, Nancy Lynch offers a blueprint for designing, imposing, and reading allotted algorithms. She directs her ebook at a large viewers, together with scholars, programmers, approach designers, and researchers.

Distributed Algorithms comprises the main major algorithms and impossibility leads to the world, all in an easy automata-theoretic surroundings. The algorithms are proved right, and their complexity is analyzed in response to accurately outlined complexity measures. the issues coated comprise source allocation, conversation, consensus between allotted tactics, info consistency, impasse detection, chief election, worldwide snapshots, and plenty of others.

The fabric is geared up based on the procedure model―first by means of the timing version after which via the interprocess verbal exchange mechanism. the cloth on approach versions is remoted in separate chapters for simple reference.

The presentation is totally rigorous, but is intuitive sufficient for fast comprehension. This booklet familiarizes readers with vital difficulties, algorithms, and impossibility ends up in the world: readers can then realize the issues after they come up in perform, observe the algorithms to unravel them, and use the impossibility effects to figure out even if difficulties are unsolvable. The booklet additionally offers readers with the fundamental mathematical instruments for designing new algorithms and proving new impossibility effects. additionally, it teaches readers find out how to cause rigorously approximately allotted algorithms―to version them officially, devise designated requisites for his or her required habit, turn out their correctness, and assessment their functionality with life like measures.

Topics in Graph Automorphisms and Reconstruction

This in-depth insurance of significant parts of graph thought keeps a spotlight on symmetry houses of graphs. usual subject matters on graph automorphisms are offered early on, whereas in later chapters extra specialized subject matters are tackled, equivalent to graphical ordinary representations and pseudosimilarity. the ultimate 4 chapters are dedicated to the reconstruction challenge, and right here specific emphasis is given to these effects that contain the symmetry of graphs, lots of which aren't to be present in different books.

Extra info for Geodesic Convexity in Graphs

Example text

If G contains a leaf, then either G ∼ = P3 in which case fc (G) = 1 or G has order at least 4, in which case con(G) = n − 1 ≥ 3. Hence, every vertex of G belongs to at least two maximum convex sets. 22 ([52]). Given any pair of integers a, b with 0 ≤ a ≤ b and 3 ≤ b, there exists a graph G such that fc (G) = a and con(G) = b. a+1 Sketch of proof. If 3 ≤ a = b, take Kb+1 . If 1 ≤ a < b, take a tree Tb+1 , with b + 1 vertices and a + 1 leaves. Suppose hence that a = 0 and 3 ≤ b. Let G be the graph depicted in Fig.

Hence, by induction hypothesis, G[S1 ] = Qr and G[S2 ] = Qs , where 0 ≤ r, s ≤ k. Take u1 ∈ S1 and v2 ∈ S2 . If u2 is the neighbor of u1 in G2 and v1 is the neighbor of v2 in G1 , then {u2 , v1 } ⊆ I[u1 , v2 ]. Hence, r = s and S = Qr+1 . 15 ([48]). Given any pair of integers n, k with 2 ≤ k ≤ n − 1, there exists a polyconvex connected graph of order n with con(G) = k. 22 a x1 2 Invariants z11 z21 b z12 z22 w2 z13 z14 w1 w2 w3 w4 y1 x2 z23 z24 y2 z1 z2 x w1 w3 z3 w4 z4 y w8 w5 w7 w6 Fig. t. t. n = 12 and con(G) = k = 8 Proof.

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 . We form convex sets of orders 2k − n − 1 and 2k − n by taking all the vertices of G3 and adding at most one vertex from each of the partite classes of order n − k of G1 and G2 . We form a convex set of orders n − k + 2 to k − 1 by taking all the vertices of G1 together with an appropriate number of adjacent vertices of G3 .

Download PDF sample

Rated 4.60 of 5 – based on 36 votes