Ch. 12: Distance
From "A First Course in Graph Theory" (Gary Chartrand, Ping Zhang) 12.1. The Center of a Graph 12.2. Distant Vertices 12.3. Excursion: Locating Numbers 12.4. Excursion: Detour and Directed Distance 12.5. Exploration: Channel Assignment 12.6. Exploration: Distance Between Graphs
86 flashcards · Mathematics · by lakesare
Part of Textbooks › A First Course in Graph Theory (Chartrand, Zhang) · 13 courses
What is the distance d(u,v)d(u, v)d(u,v) between two vertices u,vu, vu,v of a connected graph, and what is a uuu – vvv geodesic?
d(u,v)d(u, v)d(u,v) = the length of a shortest uuu – vvv path; a uuu – vvv geodesic is a uuu – vvv path of length d(u,v)d(u, v)d(u,v) . GGG must be connected for d(u,v)d(u, v)d(u,v) to be defined for every pair.
Which four properties make the distance ddd of a connected graph GGG a metric on V(G)V(G)V(G) ?
d(u,v)≥0d(u, v) \ge 0d(u,v)≥0 ; d(u,v)=0 ⟺ u=v\ d(u, v) = 0 \iff u = v d(u,v)=0⟺u=v ; d(u,v)=d(v,u)\ d(u, v) = d(v, u) d(u,v)=d(v,u) ; d(u,w)≤d(u,v)+d(v,w)\ d(u, w) \le d(u, v) + d(v, w) d(u,w)≤d(u,v)+d(v,w) . The last two are the symmetric property and the triangle inequality. So (V(G),d)(V(G), d)(V(G),d) is a metric space.
Why does graph distance satisfy the triangle inequality d(u,w)≤d(u,v)+d(v,w)d(u, w) \le d(u, v) + d(v, w)d(u,w)≤d(u,v)+d(v,w) ?
A uuu – vvv geodesic followed by a vvv – www geodesic is a uuu – www walk of length d(u,v)+d(v,w)d(u, v) + d(v, w)d(u,v)+d(v,w) , and every uuu – www walk contains a uuu – www path that is no longer.
What is the eccentricity e(v)e(v)e(v) of a vertex vvv in a connected graph GGG ?
The distance between vvv and a vertex farthest from vvv , i.e. e(v)=maxx∈V(G)d(v,x)e(v) = \max_{x \in V(G)} d(v, x)e(v)=maxx∈V(G)d(v,x) .
What are the radius rad(G)\operatorname{rad}(G)rad(G) and the diameter diam(G)\operatorname{diam}(G)diam(G) of a connected graph GGG ?
rad(G)\operatorname{rad}(G)rad(G) = the minimum eccentricity, diam(G)\operatorname{diam}(G)diam(G) = the maximum eccentricity among the vertices of GGG . So diam(G)\operatorname{diam}(G)diam(G) is also the greatest distance between two vertices.
What is a central vertex of a connected graph GGG , and what is the center Cen(G)\operatorname{Cen}(G)Cen(G) ?
A central vertex is a vertex vvv with e(v)=rad(G)e(v) = \operatorname{rad}(G)e(v)=rad(G) ; Cen(G)\operatorname{Cen}(G)Cen(G) is the subgraph induced by the central vertices. Each vertex labelled with its eccentricity: rad(H)=2\operatorname{rad}(H) = 2rad(H)=2 , diam(H)=4\operatorname{diam}(H) = 4diam(H)=4 , Cen(H)=K2\operatorname{Cen}(H) = K_2Cen(H)=K2 .
When is a connected graph GGG self-centered? Give an example.
When every vertex is central, i.e. Cen(G)=G\operatorname{Cen}(G) = GCen(G)=G (all eccentricities equal). e.g. every cycle CnC_nCn , n≥3n \ge 3n≥3 .
A town wants to build its firehouse at a street intersection so that no location is too far from it. In the graph modelling the streets (vertices = intersections), where should it go?
At a central vertex (a vertex of minimum eccentricity). Each intersection labelled with its eccentricity: the three black vertices have eccentricity 5, the radius.
For circles, the diameter is twice the radius. Does diam(G)=2rad(G)\operatorname{diam}(G) = 2 \operatorname{rad}(G)diam(G)=2rad(G) hold for every connected graph GGG ?
No. There is no identity relating the radius and the diameter. Each GkG_kGk has radius 2 and diameter kkk , for k=2,3,4k = 2, 3, 4k=2,3,4 .
Theorem 12.1 For every nontrivial connected graph GGG : ?≤diam(G)≤ ?\quad ? \le \operatorname{diam}(G) \le \; ??≤diam(G)≤?
rad(G)≤diam(G)≤2rad(G)\boldsymbol{\operatorname{rad}(G)} \le \operatorname{diam}(G) \le \boldsymbol{2 \operatorname{rad}(G)}rad(G)≤diam(G)≤2rad(G)
Why is diam(G)≤2rad(G)\operatorname{diam}(G) \le 2 \operatorname{rad}(G)diam(G)≤2rad(G) for every connected graph GGG ( rad\operatorname{rad}rad = minimum eccentricity, diam\operatorname{diam}diam = maximum eccentricity)?
Take u,vu, vu,v with d(u,v)=diam(G)d(u, v) = \operatorname{diam}(G)d(u,v)=diam(G) and a central vertex www : d(u,v)≤d(u,w)+d(w,v)≤2rad(G)\ d(u, v) \le d(u, w) + d(w, v) \le 2 \operatorname{rad}(G) d(u,v)≤d(u,w)+d(w,v)≤2rad(G) . www is within distance e(w)=rad(G)e(w) = \operatorname{rad}(G)e(w)=rad(G) of every vertex.
Theorem 12.2. uuu and vvv are adjacent vertices of a connected graph. How far apart can their eccentricities e(u),e(v)e(u), e(v)e(u),e(v) be?
∣e(u)−e(v)∣≤1\boldsymbol{|e(u) - e(v)| \le 1}∣e(u)−e(v)∣≤1 If xxx is farthest from uuu : e(u)=d(u,x)≤d(u,v)+d(v,x)≤1+e(v)e(u) = d(u, x) \le d(u, v) + d(v, x) \le 1 + e(v)e(u)=d(u,x)≤d(u,v)+d(v,x)≤1+e(v) , and symmetrically.
Theorem 12.3. uuu and vvv are adjacent vertices of a connected graph GGG , and xxx is any vertex of GGG . How do d(u,x)d(u, x)d(u,x) and d(v,x)d(v, x)d(v,x) compare?
∣d(u,x)−d(v,x)∣≤1\boldsymbol{|d(u, x) - d(v, x)| \le 1}∣d(u,x)−d(v,x)∣≤1 By the triangle inequality, d(u,x)≤1+d(v,x)d(u, x) \le 1 + d(v, x)d(u,x)≤1+d(v,x) and d(v,x)≤1+d(u,x)d(v, x) \le 1 + d(u, x)d(v,x)≤1+d(u,x) .
Theorem 12.4. Which graphs are the center of some graph?
Every graph. Proved by Stephen Hedetniemi.
Every graph is the center of some graph.Given a graph GGG , how does the proof build a graph FFF with Cen(F)=G\operatorname{Cen}(F) = GCen(F)=G ?
Add two new vertices u,vu, vu,v joined to every vertex of GGG (not to each other), then a pendant vertex u1u_1u1 at uuu and v1v_1v1 at vvv . Eccentricities: e(u1)=e(v1)=4e(u_1) = e(v_1) = 4e(u1)=e(v1)=4 , e(u)=e(v)=3e(u) = e(v) = 3e(u)=e(v)=3 , and 2 for every vertex of GGG .
Who was Stephen Hedetniemi's graph theory teacher and doctoral co-supervisor?
Frank Harary (PhD at the University of Michigan, 1966). Hedetniemi showed that every graph is the center of some graph; his other co-supervisor was John Holland, later the founder of genetic algorithms.
Theorem 12.5. Where in a connected graph GGG must the center Cen(G)\operatorname{Cen}(G)Cen(G) (the subgraph induced by the vertices of minimum eccentricity) lie?
Inside a single block of GGG . A block is a maximal connected subgraph without cut-vertices.
The center of every connected graph GGG is a subgraph of some block of GGG .What is the key idea of the proof?
Otherwise a cut-vertex vvv separates central vertices: then some central vertex www is on the far side of vvv from a vertex uuu with d(u,v)=e(v)d(u, v) = e(v)d(u,v)=e(v) , so e(w)≥d(u,w)>d(u,v)=e(v)e(w) \ge d(u, w) > d(u, v) = e(v)e(w)≥d(u,w)>d(u,v)=e(v) . Every uuu – www path passes through vvv . So www is not central, a contradiction.
What is a peripheral vertex of a connected graph GGG , and what is the periphery Per(G)\operatorname{Per}(G)Per(G) ?
A peripheral vertex is a vertex vvv with e(v)=diam(G)e(v) = \operatorname{diam}(G)e(v)=diam(G) ; Per(G)\operatorname{Per}(G)Per(G) is the subgraph induced by the peripheral vertices. Here Per(H)=2K1\operatorname{Per}(H) = 2K_1Per(H)=2K1 , two isolated vertices.
Is the periphery Per(G)\operatorname{Per}(G)Per(G) (subgraph induced by the vertices of maximum eccentricity) of a connected graph always disconnected?
No. Each vertex labelled with its eccentricity: diam(F)=3\operatorname{diam}(F) = 3diam(F)=3 and Per(F)=C6\operatorname{Per}(F) = C_6Per(F)=C6 . Also Per(Cn)=Cn\operatorname{Per}(C_n) = C_nPer(Cn)=Cn .
Theorem 12.6 (Bielak, Sysło) A nontrivial graph GGG is the periphery of some graph if and only if … ?
Every vertex of GGG has eccentricity 1, or no vertex of GGG has eccentricity 1. So, unlike centers, not every graph is a periphery: e.g. no star K1,tK_{1, t}K1,t with t≥2t \ge 2t≥2 .
GGG is a graph in which no vertex has eccentricity 1 (every vertex has a non-neighbor). How do you build a graph HHH with periphery Per(H)=G\operatorname{Per}(H) = GPer(H)=G ?
Add a new vertex www joined to every vertex of GGG . Then eH(w)=1e_H(w) = 1eH(w)=1 and eH(x)=2e_H(x) = 2eH(x)=2 for every xxx in GGG , so the peripheral vertices of HHH are exactly those of GGG .
GGG has a vertex xxx adjacent to all other vertices of GGG , but GGG is not complete. Suppose Per(H)=G\operatorname{Per}(H) = GPer(H)=G for some graph HHH , so every vertex of GGG has eH=diam(H)=k≥2e_H = \operatorname{diam}(H) = k \ge 2eH=diam(H)=k≥2 .Why is this impossible?
A vertex www at distance kkk from xxx is not adjacent to xxx , so w∉Gw \notin Gw∈/G ; but eH(w)≥d(w,x)=ke_H(w) \ge d(w, x) = keH(w)≥d(w,x)=k , so www is peripheral too. This is the hard direction of: GGG is a periphery if and only if all or none of its vertices have eccentricity 1.
What is an eccentric vertex of a vertex uuu , and what is an eccentric vertex of the graph GGG ?
An eccentric vertex of uuu is a vertex farthest from uuu , i.e. vvv with d(u,v)=e(u)d(u, v) = e(u)d(u,v)=e(u) . An eccentric vertex of GGG is an eccentric vertex of some vertex of GGG . vvv is an eccentric vertex of uuu ( d(u,v)=3=e(u)d(u, v) = 3 = e(u)d(u,v)=3=e(u) ), but uuu is not an eccentric vertex of vvv , since e(v)=4e(v) = 4e(v)=4 .
yyy is an eccentric vertex of xxx (a vertex farthest from xxx ) in a connected graph. How do e(y)e(y)e(y) and e(x)e(x)e(x) compare?
e(y)≥e(x)\boldsymbol{e(y) \ge e(x)}e(y)≥e(x) e(y)≥d(y,x)=e(x)e(y) \ge d(y, x) = e(x)e(y)≥d(y,x)=e(x) .
Is every peripheral vertex ( e(x)=diam(G)e(x) = \operatorname{diam}(G)e(x)=diam(G) ) an eccentric vertex of GGG (farthest from some vertex)? And conversely?
Yes; the converse is false. If d(x,y)=e(x)=diam(G)d(x, y) = e(x) = \operatorname{diam}(G)d(x,y)=e(x)=diam(G) , then yyy is peripheral too and xxx is farthest from yyy . vvv is an eccentric vertex of uuu , but e(v)=4<5=diam(G)e(v) = 4 < 5 = \operatorname{diam}(G)e(v)=4<5=diam(G) .
When is a connected graph an eccentric graph?
When every vertex is an eccentric vertex (farthest from some vertex). Every self-centered graph is eccentric, but not conversely: Every vertex is eccentric, yet the eccentricities (labels) are 2, 3 and 4.
What is the eccentric subgraph Ecc(G)\operatorname{Ecc}(G)Ecc(G) of a connected graph GGG ?
The subgraph induced by the eccentric vertices of GGG (vertices farthest from some vertex). Here Ecc(F)=2P3\operatorname{Ecc}(F) = 2P_3Ecc(F)=2P3 .
Theorem 12.7 A nontrivial graph GGG is the eccentric subgraph of some graph if and only if … ?
Every vertex of GGG has eccentricity 1, or no vertex of GGG has eccentricity 1, the same condition as for peripheries. If no vertex has eccentricity 1, add a vertex www joined to all of GGG : every vertex of GGG is farthest from www , and www is farthest from nothing.Caveat: the book's proof only rules out graphs H≠GH \ne GH=G . K4−eK_4 - eK4−e (two vertices of eccentricity 1, two of eccentricity 2) is an eccentric graph, so it is its own eccentric subgraph.
What is a boundary vertex of a vertex uuu , and a boundary vertex of the graph GGG ?
vvv is a boundary vertex of uuu if d(u,w)≤d(u,v)d(u, w) \le d(u, v)d(u,w)≤d(u,v) for every neighbor www of vvv ; a boundary vertex of GGG is a boundary vertex of some vertex. So d(u,⋅)d(u, \cdot)d(u,⋅) has a local maximum at vvv : no uuu – vvv geodesic can be extended at vvv to a longer geodesic.
How are peripheral, eccentric and boundary vertices of a connected graph related?
Peripheral ⇒\Rightarrow⇒ eccentric ⇒\Rightarrow⇒ boundary, and neither converse holds. zzz is an eccentric vertex of www , but not peripheral; www is a boundary vertex of sss , but not an eccentric vertex of any vertex.
Theorem 12.8. Can a cut-vertex be a boundary vertex of a connected graph?
No. If vvv is a cut-vertex and u≠vu \ne vu=v , a neighbor www of vvv in a component of G−vG - vG−v not containing uuu has d(u,w)=d(u,v)+1d(u, w) = d(u, v) + 1d(u,w)=d(u,v)+1 .Hence no cut-vertex is an eccentric or peripheral vertex either.
What is a complete vertex (also extreme or simplicial vertex)?
A vertex whose neighbors induce a complete subgraph. e.g. every end-vertex.
Theorem 12.9. In a connected graph GGG , which vertices vvv are a boundary vertex of every vertex u≠vu \ne vu=v ?
Exactly the complete vertices (whose neighbors are pairwise adjacent).
In a connected graph, vvv is a boundary vertex of uuu if d(u,w)≤d(u,v)d(u, w) \le d(u, v)d(u,w)≤d(u,v) for every neighbor www of vvv .Why is a complete vertex vvv (neighbors pairwise adjacent) a boundary vertex of every u≠vu \ne vu=v ?
Take a uuu – vvv geodesic (u,…,vk−1,v)(u, \dots, v_{k-1}, v)(u,…,vk−1,v) : every other neighbor www of vvv is adjacent to vk−1v_{k-1}vk−1 , so (u,…,vk−1,w)(u, \dots, v_{k-1}, w)(u,…,vk−1,w) shows d(u,w)≤k=d(u,v)d(u, w) \le k = d(u, v)d(u,w)≤k=d(u,v) . Conversely, if vvv has nonadjacent neighbors u,wu, wu,w , then d(u,w)=2>d(u,v)d(u, w) = 2 > d(u, v)d(u,w)=2>d(u,v) , so vvv is not a boundary vertex of uuu .
Theorem 12.10. uuu is a vertex of a nontrivial connected graph. When is every vertex other than uuu a boundary vertex of uuu ?
Exactly when e(u)=1e(u) = 1e(u)=1 ( uuu is adjacent to all other vertices). If e(u)≥2e(u) \ge 2e(u)≥2 , some xxx has d(u,x)=2d(u, x) = 2d(u,x)=2 ; on a geodesic (u,y,x)(u, y, x)(u,y,x) , yyy is not a boundary vertex of uuu , since its neighbor xxx is farther from uuu .
When does a vertex yyy lie between two vertices xxx and zzz ?
When d(x,z)=d(x,y)+d(y,z)d(x, z) = d(x, y) + d(y, z)d(x,z)=d(x,y)+d(y,z) ( y≠x,zy \ne x, zy=x,z ), i.e. the triangle inequality is an equality. Equivalently, yyy lies on some xxx – zzz geodesic.
What is an interior vertex of a connected graph GGG , and what is the interior Int(G)\operatorname{Int}(G)Int(G) ?
vvv is interior if for every vertex u≠vu \ne vu=v there is a vertex www such that vvv lies between uuu and www ; Int(G)\operatorname{Int}(G)Int(G) is the subgraph induced by the interior vertices. sss , vvv , xxx are the interior vertices, so Int(G)=P3\operatorname{Int}(G) = P_3Int(G)=P3 .
Theorem 12.11. How are the boundary vertices and the interior vertices of a connected graph related?
A vertex is a boundary vertex if and only if it is not an interior vertex.
vvv is a boundary vertex of uuu if no neighbor of vvv is farther from uuu than vvv . vvv is an interior vertex if for every u≠vu \ne vu=v some www has d(u,w)=d(u,v)+d(v,w)d(u, w) = d(u, v) + d(v, w)d(u,w)=d(u,v)+d(v,w) .Why can't a boundary vertex vvv (of uuu ) be interior?
vvv would lie on a uuu – www geodesic for some www , and the vertex after vvv on it is a neighbor of vvv at distance d(u,v)+1d(u, v) + 1d(u,v)+1 from uuu . Conversely, if vvv is between uuu and no vertex, every neighbor xxx of vvv has d(u,x)<d(u,v)+1d(u, x) < d(u, v) + 1d(u,x)<d(u,v)+1 , so vvv is a boundary vertex of uuu .
W={w1,…,wk}W = \{w_1, \dots, w_k\}W={w1,…,wk} is an ordered set of vertices of a connected graph GGG . What is the locating code cW(v)c_W(v)cW(v) of a vertex vvv ?
cW(v)=(d(v,w1),d(v,w2),…,d(v,wk))\boldsymbol{c_W(v) = (d(v, w_1), d(v, w_2), \dots, d(v, w_k))}cW(v)=(d(v,w1),d(v,w2),…,d(v,wk)) , the vector of distances from vvv to the vertices of WWW .
When is an ordered set WWW of vertices of a connected graph a locating set (or resolving set)?
When distinct vertices have distinct codes cW(v)=(d(v,w1),…,d(v,wk))c_W(v) = (d(v, w_1), \dots, d(v, w_k))cW(v)=(d(v,w1),…,d(v,wk)) . So every vertex is determined by its distances to WWW . Peter Slater described these ideas for U.S. sonar and Coast Guard Loran stations.
What is the location number loc(G)\operatorname{loc}(G)loc(G) (also metric dimension) of a connected graph, and what is a metric basis?
loc(G)\operatorname{loc}(G)loc(G) = the minimum size of a locating set; a metric basis is a locating set of that size (a minimum locating set). A locating set WWW : distinct vertices have distinct codes (d(v,w1),…,d(v,wk))(d(v, w_1), \dots, d(v, w_k))(d(v,w1),…,d(v,wk)) .
Is {v1,v3}\{v_1, v_3\}{v1,v3} a locating set (distinct vertices get distinct distance vectors)? What is loc(G)\operatorname{loc}(G)loc(G) ?
No: v2v_2v2 and v4v_4v4 both get (1,1)(1, 1)(1,1) . loc(G)=2\operatorname{loc}(G) = 2loc(G)=2 . W={v1,v2}W = \{v_1, v_2\}W={v1,v2} gives v1:(0,1)v_1: (0, 1)v1:(0,1) , v2:(1,0)v_2: (1, 0)v2:(1,0) , v3:(2,1)v_3: (2, 1)v3:(2,1) , v4:(1,2)v_4: (1, 2)v4:(1,2) , v5:(1,1)v_5: (1, 1)v5:(1,1) , and no single vertex works.Rooms as vertices: two sensors that report the distance to an intruder are enough to locate them.
GGG is a connected graph of order n≥2n \ge 2n≥2 . What are the general bounds on loc(G)\operatorname{loc}(G)loc(G) (minimum size of a locating set)?
1≤loc(G)≤n−1\boldsymbol{1 \le \operatorname{loc}(G) \le n - 1}1≤loc(G)≤n−1 W=V(G)−{v}W = V(G) - \{v\}W=V(G)−{v} is locating: each wiw_iwi is the only vertex with 0 in coordinate iii , and vvv is the only vertex with no 0.
Theorem 12.12. Which connected graphs GGG of order nnn have loc(G)=1\operatorname{loc}(G) = 1loc(G)=1 (one vertex whose distances tell all vertices apart)?
Only the path PnP_nPn . An end-vertex of PnP_nPn works. Conversely, if {w}\{w\}{w} is locating, the nnn distances d(v,w)d(v, w)d(v,w) are distinct values in 0,…,n−10, \dots, n - 10,…,n−1 , so some vertex is at distance n−1n - 1n−1 : diam(G)=n−1\operatorname{diam}(G) = n - 1diam(G)=n−1 , forcing G=PnG = P_nG=Pn .
Theorem 12.13. Which connected graphs GGG of order n≥2n \ge 2n≥2 have loc(G)=n−1\operatorname{loc}(G) = n - 1loc(G)=n−1 ?
Only the complete graph KnK_nKn . In KnK_nKn every vertex outside WWW has code (1,…,1)(1, \dots, 1)(1,…,1) . If G≠KnG \ne K_nG=Kn , take u,vu, vu,v with d(u,v)=2d(u, v) = 2d(u,v)=2 and a geodesic (u,x,v)(u, x, v)(u,x,v) : W=V(G)−{x,v}W = V(G) - \{x, v\}W=V(G)−{x,v} is locating, since d(x,u)=1≠2=d(v,u)d(x, u) = 1 \ne 2 = d(v, u)d(x,u)=1=2=d(v,u) .
Theorem 12.14. GGG is a connected graph of order n≥2n \ge 2n≥2 , diameter ddd and maximum degree Δ\DeltaΔ . Bound loc(G)\operatorname{loc}(G)loc(G) (minimum size of a locating set) from both sides.
⌈log3(Δ+1)⌉≤loc(G)≤n−d\boldsymbol{\lceil \log_3(\Delta + 1) \rceil \le \operatorname{loc}(G) \le n - d}⌈log3(Δ+1)⌉≤loc(G)≤n−d Both bounds are sharp for PnP_nPn ( Δ=2\Delta = 2Δ=2 , d=n−1d = n - 1d=n−1 , loc=1\operatorname{loc} = 1loc=1 ); KnK_nKn attains the upper bound.
loc(G)≤n−d\operatorname{loc}(G) \le n - dloc(G)≤n−d for a connected graph GGG of order nnn and diameter ddd .Which locating set of size n−dn - dn−d does the proof use?
Take a geodesic (u=v0,v1,…,vd)(u = v_0, v_1, \dots, v_d)(u=v0,v1,…,vd) of length ddd and let W=V(G)−{v1,…,vd}W = V(G) - \{v_1, \dots, v_d\}W=V(G)−{v1,…,vd} . u∈Wu \in Wu∈W and d(vi,u)=id(v_i, u) = id(vi,u)=i , so the vertices outside WWW have distinct codes.
loc(G)≥log3(Δ+1)\operatorname{loc}(G) \ge \log_3(\Delta + 1)loc(G)≥log3(Δ+1) for a connected graph GGG with maximum degree Δ\DeltaΔ .What is the counting argument, for a locating set W={w1,…,wk}W = \{w_1, \dots, w_k\}W={w1,…,wk} and a vertex vvv of degree Δ\DeltaΔ ?
Each coordinate d(u,wi)d(u, w_i)d(u,wi) of a neighbor uuu of vvv is d(v,wi)−1d(v, w_i) - 1d(v,wi)−1 , d(v,wi)d(v, w_i)d(v,wi) or d(v,wi)+1d(v, w_i) + 1d(v,wi)+1 , and not all equal d(v,wi)d(v, w_i)d(v,wi) , so the Δ\DeltaΔ distinct neighbor codes are among 3k−13^k - 13k−1 vectors. So Δ≤3k−1\Delta \le 3^k - 1Δ≤3k−1 . Adjacent vertices have distances to any xxx that differ by at most 1.
When are two vertices u,vu, vu,v of a connected graph distance similar?
When d(u,x)=d(v,x)d(u, x) = d(v, x)d(u,x)=d(v,x) for every vertex x≠u,vx \ne u, vx=u,v . Equivalently: uv∉E(G)uv \notin E(G)uv∈/E(G) and N(u)=N(v)N(u) = N(v)N(u)=N(v) , or uv∈E(G)uv \in E(G)uv∈E(G) and N[u]=N[v]N[u] = N[v]N[u]=N[v] (closed neighborhoods).
Distance similarity (same distance to every other vertex) is an equivalence relation on V(G)V(G)V(G) . What can each equivalence class induce?
Either an independent set or a complete subgraph.
GGG is a connected graph of order nnn whose vertices fall into kkk distance similar classes (two vertices are distance similar if they have the same distance to every other vertex). What lower bound on loc(G)\operatorname{loc}(G)loc(G) follows, and why?
loc(G)≥n−k\boldsymbol{\operatorname{loc}(G) \ge n - k}loc(G)≥n−k Two distance similar vertices outside a set WWW get the same code, so every locating set contains all but at most one vertex of each class.
If the vertices of a connected graph GGG of order nnn fall into kkk distance similar classes, then loc(G)≥n−k\operatorname{loc}(G) \ge n - kloc(G)≥n−k .Is this bound always attained?
No. n=9n = 9n=9 with classes {x1,y1}\{x_1, y_1\}{x1,y1} , {x2,y2}\{x_2, y_2\}{x2,y2} and 5 singletons, so n−k=2n - k = 2n−k=2 ; but {x1,x2}\{x_1, x_2\}{x1,x2} gives y3,y4y_3, y_4y3,y4 the same code (1,3)(1, 3)(1,3) , and loc(H)=3\operatorname{loc}(H) = 3loc(H)=3 .
What is the detour distance D(u,v)D(u, v)D(u,v) in a connected graph, and what is a uuu – vvv detour?
D(u,v)D(u, v)D(u,v) = the length of a longest uuu – vvv path; a uuu – vvv detour is a uuu – vvv path of length D(u,v)D(u, v)D(u,v) . Here d(u,v)=3d(u, v) = 3d(u,v)=3 but D(u,v)=8D(u, v) = 8D(u,v)=8 (the bold path).
Theorem 12.15. Is detour distance DDD (length of a longest path) a metric on the vertex set of every connected graph?
Yes. The only nontrivial property is the triangle inequality D(u,w)≤D(u,v)+D(v,w)D(u, w) \le D(u, v) + D(v, w)D(u,w)≤D(u,v)+D(v,w) .
PPP is a uuu – www detour (longest uuu – www path), of length D(u,w)D(u, w)D(u,w) , and vvv is a vertex not on PPP .Why is D(u,w)<D(u,v)+D(v,w)D(u, w) < D(u, v) + D(v, w)D(u,w)<D(u,v)+D(v,w) ?
A shortest path QQQ (length r>0r > 0r>0 ) from vvv to PPP , meeting it at xxx , gives a uuu – vvv path of length a+ra + ra+r and a vvv – www path of length b+rb + rb+r , where a,ba, ba,b are the lengths of the uuu – xxx and xxx – www parts of PPP . So D(u,w)=a+b<(a+r)+(b+r)≤D(u,v)+D(v,w)D(u, w) = a + b < (a + r) + (b + r) \le D(u, v) + D(v, w)D(u,w)=a+b<(a+r)+(b+r)≤D(u,v)+D(v,w) . If vvv is on PPP , split PPP at vvv instead.
What are the detour eccentricity eD(v)e_D(v)eD(v) , detour radius radD(G)\operatorname{rad}_D(G)radD(G) and detour diameter diamD(G)\operatorname{diam}_D(G)diamD(G) ?
eD(v)e_D(v)eD(v) = the maximum detour distance from vvv ; radD(G)\operatorname{rad}_D(G)radD(G) and diamD(G)\operatorname{diam}_D(G)diamD(G) = the minimum and maximum of eDe_DeD . Detour distance D(u,v)D(u, v)D(u,v) is the length of a longest uuu – vvv path.
Theorem 12.16. For a nontrivial connected graph GGG , how is the detour diameter diamD(G)\operatorname{diam}_D(G)diamD(G) bounded by the detour radius radD(G)\operatorname{rad}_D(G)radD(G) ?
radD(G)≤diamD(G)≤2radD(G)\boldsymbol{\operatorname{rad}_D(G) \le \operatorname{diam}_D(G) \le 2 \operatorname{rad}_D(G)}radD(G)≤diamD(G)≤2radD(G) Same proof as for ordinary distance: detour distance is a metric, so it obeys the triangle inequality through a vertex www with eD(w)=radD(G)e_D(w) = \operatorname{rad}_D(G)eD(w)=radD(G) .
Theorem 12.17. For which pairs a,ba, ba,b of positive integers is there a connected graph with detour radius aaa and detour diameter bbb ?
Exactly when a≤b≤2aa \le b \le 2aa≤b≤2a .
For a<b≤2aa < b \le 2aa<b≤2a , which graph has detour radius aaa and detour diameter bbb ?
Ka+1K_{a+1}Ka+1 and Kb−a+1K_{b-a+1}Kb−a+1 glued at one vertex vvv (order b+1b + 1b+1 ). a=3a = 3a=3 , b=5b = 5b=5 . eD(v)=ae_D(v) = aeD(v)=a because b−a≤ab - a \le ab−a≤a ; every other vertex starts a Hamiltonian path, so has detour eccentricity bbb . (For a=ba = ba=b : Ka+1K_{a+1}Ka+1 .)
In a connected graph, every integer between rad(G)\operatorname{rad}(G)rad(G) and diam(G)\operatorname{diam}(G)diam(G) is the eccentricity of some vertex. Is the same true for detour eccentricities eDe_DeD ?
No. In Ka+1K_{a+1}Ka+1 and Kb−a+1K_{b-a+1}Kb−a+1 glued at a vertex ( a<b≤2aa < b \le 2aa<b≤2a ), every detour eccentricity is aaa or bbb .
What is the directed distance d⃗(u,v)\vec{d}(u, v)d(u,v) in a digraph DDD , and why do we usually assume DDD is strong?
d⃗(u,v)\vec{d}(u, v)d(u,v) = the length of a shortest directed uuu – vvv path. Being connected does not guarantee a directed uuu – vvv path; being strong does.
Is directed distance d⃗\vec{d}d (length of a shortest directed path) a metric on the vertex set of a nontrivial strong digraph?
No: it is not symmetric, though it does satisfy the triangle inequality. d⃗(u,v)=1\vec{d}(u, v) = 1d(u,v)=1 but d⃗(v,u)=2\vec{d}(v, u) = 2d(v,u)=2 .
In a strong digraph DDD , what are the eccentricity e(v)e(v)e(v) , the radius rad(D)\operatorname{rad}(D)rad(D) and the diameter diam(D)\operatorname{diam}(D)diam(D) ?
e(v)e(v)e(v) = the largest directed distance d⃗(v,x)\vec{d}(v, x)d(v,x) from vvv ; rad(D)\operatorname{rad}(D)rad(D) , diam(D)\operatorname{diam}(D)diam(D) = the minimum and maximum eccentricity.
In a strong digraph DDD (with directed distance), must diam(D)≤2rad(D)\operatorname{diam}(D) \le 2 \operatorname{rad}(D)diam(D)≤2rad(D) ? Must the eccentricities of adjacent vertices differ by at most 1?
No to both: for any r≤dr \le dr≤d there is a strong digraph with radius rrr and diameter ddd . A directed cycle Cr+1C_{r+1}Cr+1 (each e(ui)=re(u_i) = re(ui)=r ) and a directed path v1,…,vdv_1, \dots, v_dv1,…,vd , with arcs from every uiu_iui to v1,…,vd−r+1v_1, \dots, v_{d-r+1}v1,…,vd−r+1 and from vdv_dvd to every uiu_iui . Then e(v1)=de(v_1) = de(v1)=d , while u1→v1u_1 \to v_1u1→v1 is an arc and e(u1)=re(u_1) = re(u1)=r .
Why does the proof of diam(G)≤2rad(G)\operatorname{diam}(G) \le 2 \operatorname{rad}(G)diam(G)≤2rad(G) (route uuu to vvv through a central vertex www ) fail for directed distance?
e(w)e(w)e(w) only bounds distances from www ; the distance d⃗(u,w)\vec{d}(u, w)d(u,w) to www can be large. Symmetry was what made d(u,w)≤e(w)d(u, w) \le e(w)d(u,w)≤e(w) .
What is the Channel Assignment Problem, and how is it usually modelled as a graph problem?
Efficiently assigning channels to transmitters. Transmitters are vertices, nearby ones are adjacent, channels are colors, with a minimum allowed separation for each pair of colors. The nearer two stations, the greater the difference in their channels must be. William Hale gave a graph model in 1980.
How are the FM radio frequencies (in the U.S.) divided into channels?
The band 88.0 to 108.0 MHz is split into 100 channels of 0.2 MHz (200 kHz). A station's frequency is the midpoint of its channel, e.g. 96.1 MHz. Stations on the same channel must be at least 115 km apart, on adjacent channels at least 72 km (depending on station classes).
GGG is a connected graph and 1≤k≤diam(G)1 \le k \le \operatorname{diam}(G)1≤k≤diam(G) . What is a radio kkk -coloring of GGG ?
A function c:V(G)→Nc: V(G) \to \mathbb{N}c:V(G)→N with d(u,v)+∣c(u)−c(v)∣≥1+kd(u, v) + |c(u) - c(v)| \ge 1 + kd(u,v)+∣c(u)−c(v)∣≥1+k for every two distinct vertices u,vu, vu,v . The closer two vertices, the more their colors must differ.
What does a radio 2-coloring ( d(u,v)+∣c(u)−c(v)∣≥3d(u, v) + |c(u) - c(v)| \ge 3d(u,v)+∣c(u)−c(v)∣≥3 for all distinct u,vu, vu,v ) require of vertices at distance 1, 2 and 3 or more?
Distance 1: colors differ by at least 2. Distance 2: colors differ. Distance ≥3\ge 3≥3 : no restriction. A radio 2-coloring with maximum color 7.
What are the value rck(c)\operatorname{rc}_k(c)rck(c) of a radio kkk -coloring ccc and the radio kkk -chromatic number rck(G)\operatorname{rc}_k(G)rck(G) ?
rck(c)\operatorname{rc}_k(c)rck(c) = the maximum color ccc uses; rck(G)\operatorname{rc}_k(G)rck(G) = the minimum value over all radio kkk -colorings of GGG . A coloring with rck(c)=rck(G)\operatorname{rc}_k(c) = \operatorname{rc}_k(G)rck(c)=rck(G) is a minimum radio kkk -coloring; it necessarily uses color 1.
HHH is a triangle with one pendant vertex attached at each of its three vertices. Find rc2(H)\operatorname{rc}_2(H)rc2(H) , where a radio 2-coloring needs colors differing by ≥2\ge 2≥2 on adjacent vertices and different colors at distance 2.
rc2(H)=6\boldsymbol{\operatorname{rc}_2(H) = 6}rc2(H)=6 With colors 1,…,51, \dots, 51,…,5 only, the triangle must get 1,3,51, 3, 51,3,5 ; the end-vertex at 3 then needs 1 or 5, but it is at distance 2 from those two vertices.
What is a radio 1-coloring of a connected graph ( d(u,v)+∣c(u)−c(v)∣≥2d(u, v) + |c(u) - c(v)| \ge 2d(u,v)+∣c(u)−c(v)∣≥2 )?
A proper vertex coloring: adjacent vertices get different colors, nothing else is required. So radio kkk -colorings generalize ordinary colorings, and rc1(G)=χ(G)\operatorname{rc}_1(G) = \chi(G)rc1(G)=χ(G) .
Radio 2-colorings are also called labelings at distance 2, or L(2, 1)-labelings.
Adjacent labels differ by at least 2, labels at distance 2 by at least 1.
What is a radio labeling of a connected graph GGG ?
A radio diam(G)\operatorname{diam}(G)diam(G) -coloring: c:V(G)→Nc: V(G) \to \mathbb{N}c:V(G)→N with d(u,v)+∣c(u)−c(v)∣≥1+diam(G)d(u, v) + |c(u) - c(v)| \ge 1 + \operatorname{diam}(G)d(u,v)+∣c(u)−c(v)∣≥1+diam(G) for all distinct u,vu, vu,v . All labels are distinct, since d(u,v)≤diam(G)d(u, v) \le \operatorname{diam}(G)d(u,v)≤diam(G) . The minimum of the largest label is the radio number rn(G)\operatorname{rn}(G)rn(G) .
Find the radio number rn(G)\operatorname{rn}(G)rn(G) of this graph of diameter 3 (labels c(u)∈Nc(u) \in \mathbb{N}c(u)∈N with d(u,v)+∣c(u)−c(v)∣≥4d(u, v) + |c(u) - c(v)| \ge 4d(u,v)+∣c(u)−c(v)∣≥4 ; minimize the largest label).
rn(G)=8\boldsymbol{\operatorname{rn}(G) = 8}rn(G)=8 With labels in 1,…,71, \dots, 71,…,7 , two pairs of labels would be consecutive (or three consecutive), but consecutive labels need distance 3, and only u,xu, xu,x are at distance 3.
ccc is a radio labeling of a connected graph with vertices v1,…,vnv_1, \dots, v_nv1,…,vn , and rn(c)\operatorname{rn}(c)rn(c) is its largest label. What is the complementary labeling cˉ\bar{c}cˉ ?
cˉ(vi)=rn(c)+1−c(vi)\boldsymbol{\bar{c}(v_i) = \operatorname{rn}(c) + 1 - c(v_i)}cˉ(vi)=rn(c)+1−c(vi) The complement of the labeling 4,1,8,6,34, 1, 8, 6, 34,1,8,6,3 ( u,v,y,w,xu, v, y, w, xu,v,y,w,x ) with rn(c)=8\operatorname{rn}(c) = 8rn(c)=8 .
Theorem 12.20. ccc is a radio labeling of a connected graph. Is its complementary labeling cˉ(vi)=rn(c)+1−c(vi)\bar{c}(v_i) = \operatorname{rn}(c) + 1 - c(v_i)cˉ(vi)=rn(c)+1−c(vi) also one?
Yes, since ∣cˉ(vi)−cˉ(vj)∣=∣c(vi)−c(vj)∣|\bar{c}(v_i) - \bar{c}(v_j)| = |c(v_i) - c(v_j)|∣cˉ(vi)−cˉ(vj)∣=∣c(vi)−c(vj)∣ . So if ccc is a minimum radio labeling, so is cˉ\bar{c}cˉ .
When can a graph GGG be rotated into a graph HHH (an edge rotation)?
When GGG has distinct vertices u,v,wu, v, wu,v,w with uv∈E(G)uv \in E(G)uv∈E(G) , uw∉E(G)uw \notin E(G)uw∈/E(G) and H≅G−uv+uwH \cong G - uv + uwH≅G−uv+uw . One edge turns around its end uuu . GGG can be rotated into HHH but not into FFF .
GGG and HHH are graphs of the same order and size. What is their rotation distance d(G,H)d(G, H)d(G,H) ?
The smallest k≥0k \ge 0k≥0 with graphs G0≅G,G1,…,Gk≅HG_0 \cong G, G_1, \dots, G_k \cong HG0≅G,G1,…,Gk≅H , each GiG_iGi rotatable into Gi+1G_{i+1}Gi+1 . A rotation replaces an edge uvuvuv by a non-edge uwuwuw . It is a metric on the graphs of a fixed order and size, measuring how close they are to isomorphic.
What is the rotation distance (fewest edge rotations uv→uwuv \to uwuv→uw ) between K3∪3K1K_3 \cup 3K_1K3∪3K1 and 3K23K_23K2 ?
3 A rotation changes two degrees by 1 each, and degrees 2,2,2,0,0,02, 2, 2, 0, 0, 02,2,2,0,0,0 must become 1,1,1,1,1,11, 1, 1, 1, 1, 11,1,1,1,1,1 : six changes by 1 in total.
What is a greatest common subgraph of two nonempty graphs G1G_1G1 and G2G_2G2 ?
A graph of maximum size isomorphic to an edge-induced subgraph of G1G_1G1 and to one of G2G_2G2 . G1,G2G_1, G_2G1,G2 need not have the same order or size, and there may be several: GGG , G′G'G′ and G′′G''G′′ are all greatest common subgraphs of G1G_1G1 and G2G_2G2 .
Theorem 12.21. GGG and HHH have order nnn and size mmm , and a greatest common subgraph of them has size sss . Bound the rotation distance d(G,H)d(G, H)d(G,H) .
d(G,H)≤2(m−s)\boldsymbol{d(G, H) \le 2(m - s)}d(G,H)≤2(m−s)
GGG and HHH have the same order and size mmm , with a greatest common subgraph of size sss ; then d(G,H)≤2(m−s)d(G, H) \le 2(m - s)d(G,H)≤2(m−s) .What is the key step of the proof?
At most two rotations turn an edge of GGG not in HHH into an edge of HHH not in GGG , so the common subgraph grows by one edge. If the two edges share a vertex, one rotation suffices. Repeat m−sm - sm−s times.
What is the rotation distance graph D(S)D(S)D(S) of a set SSS of graphs of the same order and size?
Its vertices are the graphs in SSS , two adjacent if their rotation distance is 1. A graph is a rotation distance graph if it is isomorphic to some D(S)D(S)D(S) , e.g. K4−eK_4 - eK4−e :