close

Вход

Забыли?

вход по аккаунту

?

281

код для вставкиСкачать
On Paths in Planar Graphs
Daniel P. Sanders*
DEPARTMENT OF MATHEMATICS
THE OHIO STATE UNIVERSITY
COLUMBUS, OHIO 43210-1174
e-mail: dsanders@math.ohio-state.edu
ABSTRACT
This paper generalizes a theorem of Thomassen on paths in planar graphs. As a corollary,
it is shown that every 4-connected planar graph has a Hamilton path between any two
c 1997 John Wiley
specified vertices x, y and containing any specified edge other than xy. & Sons, Inc.
1. INTRODUCTION
In 1956, Tutte [5] showed that every 4-connected planar graph has a Hamilton circuit. He proved
this by showing that every plane graph has a special kind of path. In this paper, it will be called a
Tutte path, and is a generalization of a Hamilton path. It is convenient to consider only 2-connected
graphs.
In a 2-connected plane graph G, the exterior circuit is the circuit bounding the infinite face
and will be denoted XG . For a subgraph H of G, the bridges of H in G are defined as follows.
A trivial bridge of H in G is an edge in E(G) \ E(H) with both ends in V (H). A non-trivial
bridge of H in G is a component K of G \ H with all vertices of H adjacent to vertices of K
added and all edges with one end in H and the other in K added. The vertices of attachment of
a bridge B of H in G are V (B) ∩ V (H). A bridge is attached to its vertices of attachment. A
path (circuit) P, subgraph of a plane graph G, is a Tutte path (circuit) if and only if each bridge
of P has at most three vertices of attachment and each bridge containing an edge of XG has at
most two vertices of attachment.
Lemma 1 (Tutte).
Let G be a 2-connected plane graph. Let x, y, and α be two vertices and
an edge, respectively, of XG . Then G has a Tutte path from x to y containing α.
* The majority of this work was completed while the author was at the Georgia Institute of
Technology.
Journal of Graph Theory Vol. 24, No. 4, 341 345 (1997)
1997 John Wiley & Sons, Inc.
c
CCC 0364-9024/97/040341-05
342 JOURNAL OF GRAPH THEORY
FIGURE 1. The edge cannot be removed from the exterior circuit.
A Tutte path in a 4-connected graph is also a Hamilton path. Tutte's Theorem follows by
choosing x and y to be adjacent. In 1983, Thomassen [4] improved this result by removing the
restriction on the location of y.
Lemma 2 (Thomassen).
Let G be a 2-connected plane graph. Let x and α be a vertex and
edge, respectively, of XG , and let y be any vertex of G distinct from x. Then G has a Tutte path
from x to y containing α.
Thomassen's Theorem that every 4-connected plane graph is Hamilton-connected easily follows from this lemma. Freeing the vertex y from being in XG allows the ends of the path to
become arbitrary, giving the necessary Hamilton paths. For a proof of Lemma 2, see [4] and [1].
The main result of this paper generalizes Lemma 2, by removing the restriction on the location
of x.
Theorem. Let G be a 2-connected plane graph. Let α be an edge of XG , and let x and y be
arbitrary distinct vertices of G. Then G has a Tutte path P from x to y containing α.
Since x and α no longer have to share a face, this allows for more powerful results. For
example, consider a 4-connected plane graph G. While Tutte's theorem shows that G contains a
Hamilton circuit through any edge of G, the theorem presented here shows that G has a Hamilton
circuit through any two edges of G. Further, let x and y be distinct vertices of G. Thomassen's
theorem gives a Hamilton path in G from x to y. The theorem above guarantees a Hamilton
path in G from x to y through any edge of G (except xy). These two results are stated below as
Corollaries 1 and 2.
Corollary 1. Let G be a 4-connected plane graph, x, y be vertices of G, and α 6= xy be an edge
of G. Then G has a Hamilton path from x to y through α.
Corollary 2. Every 4-connected plane graph has a Hamilton circuit through any two of its edges.
The theorem above is as strong as possible in several ways.
The edge α cannot be removed from XG , even if the vertices x and y are required to be on
XG . In the graph of Figure 1, there is no Tutte path between the marked vertices containing the
marked edge.
Keeping α on XG , the direction that α is traversed cannot be specified, even if the vertices x
and y are again both on XG . This is easily seen from planarity.
In general, there is no theorem to find a path through two edges of XG , even if the vertices x
and y are both required to be on the exterior circuit. Consider the circuit C4 with vertices a, b, c, d
ON PATHS IN PLANAR GRAPHS 343
and edges ab, ad, bc, cd, embedded in the plane. There is no Tutte path in C4 from a to c through
both ab and either ad or cd. Let D := C4 + bd, with bd embedded in the interior face of C4 . Then
D has no Tutte path from a to c through both ab and bc. On the other hand, given a subset S of
E(XG ), it may be possible to classify the structure of 2-connected plane graphs that do not have
a Tutte path from x to y containing S. As a corollary, this would give necessary and sufficient
conditions for a 2-connected plane graph without interior component 3-cuts (see [2]) to have a
Hamilton circuit.
2. A PROOF OF THE THEOREM
One more lemma is required. It is a useful tool for many planar problems, and will be referred to
as the Three Edge Lemma. For a proof, see [2] or [3].
The Three Edge Lemma.
three edges of XG .
Every 2-connected plane graph G has a Tutte circuit through any
If P is a path, and x and y are two vertices of P, then xP y will represent the subpath of P
from x to y. If H and J are subgraphs of a graph G, then an H, J-connector in G is a bridge of
H ∪ J in G with vertices of attachment in both H and J.
Proof of the Theorem. The proof is by induction on the number of vertices of G. Clearly,
the theorem is true for |V (G)| ≤ 4. Let 2-connected plane G be given. Let α be an arbitrary edge
of XG , and let x and y be arbitrary vertices of G. From Lemma 2, the theorem follows trivially
if x or y is a vertex of XG , so assume not. Also, if there is an edge ψ ∈ E(G) such that x or y is
a vertex of XG−ψ , then the theorem follows trivially if Lemma 2 is applied correctly to G − ψ,
so assume not. A Tutte path in a graph H with |V (H)| < |V (G)| from u through ω to v found
by induction will be called a uωv-path in H.
Assume first that there are subgraphs L and R of G such that L ∪ R = G, V (L) ∩ V (R) =
{a, b} ⊂ V (XG ), x ∈ V (L), α ∈ E(L), y ∈ V (R), and R is 2-connected (or a similar structure
with x and y swapped). Let c 6∈ V (G) be given. Let β := ab, L0 := L + c + ac + bc, with
c embedded where R used to be, and R0 := R + β, with β embedded where L used to be.
Since R is 2-connected, and y 6∈ V (XR0 ), |V (R)| ≥ 4, and thus |V (L0 )| < |V (G)|. Since
x ∈ V (L), |V (R)| = |V (R0 )| < |V (G). Find an xαc-path PL in L0 by induction. Without loss
of generality, assume b ∈ V (PL ).
Case 1. a 6∈ V (PL ).
Let γ be an edge of XR containing a and PR be a bγy-path in R by induction. Then set
P := xPL b ∪ bPR y.
Case 2. a ∈ V (PL ).
Let PR be an aβy-path in R0 by induction. Then set P := xPL b ∪ bPR y.
The path P is as desired in each case.
If there are no such L and R as above, then x and y are in the same component of G \ XG .
From elementary graph theory, there is a ‘‘path’’of blocks of G \ XG , the first having x as a
vertex and the last having y as a vertex. Let B1 , B2 , . . . , Bk be the unique such ‘‘path’’of blocks
of G \ XG with x ∈ V (B1 ), y ∈ V (Bk ), and k minimal. Let b0 := x, bi := Bi ∩ Bi+1 for
Sk
i := 1, . . . , k − 1, bk := y, and H := i=1 Bi .
The (XG ∪ H)-bridges will now be grouped. Let s be a vertex of XG which shares a face with
a vertex of H. For each (XG ∪ H)-bridge X, let QX be the minimal path in XG including all the
vertices of attachment of X in XG such that s is not an interior vertex of QX . Further, let pX (qX )
be the most counterclockwise (clockwise) vertex of QK . Note that for two (XG ∪ H)-bridges
344 JOURNAL OF GRAPH THEORY
X, Y, either QX ⊂ QY , QY ⊂ QX , or E(QX ) ∩ E(QY ) = ∅. Let an (XG ∪ H)-bridge X be
maximal if there is no (XG ∪ H)-bridge Y distinct from X such that QX ⊂ QY , and QX 6= QY .
Let the group of a maximal (XG ∪ H)-bridge X be the union of X and all (XG ∪ H)-bridges
Y such that QY ⊂ QX , and QY 6= QX . Let the (XG ∪ H)-bridge groups be the groups of its
maximal bridges.
For each XG , H-connector group K, let vK be the unique vertex of attachment of K in H
and iK (jK ) be the least (greatest) integer such that vK ∈ V (BiK ) (∈ V (BjK )). Let Kα be the
XG , H-connector group such that α ∈ E(QKα ), or if there is none, an XG , H-connector group
with pKα nearest to α counterclockwise from it.
Since G is 2-connected, exchanging clockwise and counterclockwise in the definitions above if
necessary, there is an XG , H-connector group K with pK 6= pKα . Let Lα be an XG , H-connector
group with qLα nearest counterclockwise to QKα such that pLα 6= pKα . Let K1 , . . . , Km be all
the XG , H-connector groups with pKi = pKα . Notice Kα = Ki for some i, and thus m ≥ 1. Let
L1 , . . . , Ln be all the XG , H-connector groups with pLj 6= pKα , qLj = qLα . Notice pLα 6= pKα ,
and thus Lα = Lj for some j, and n ≥ 1.
Let a1 and a2 be vertices not in G, and let γ := a1 a2 , δi := a1 vKi , and j := a2 vLj .
Let f := min{min{jKi |1 ≤ i ≤ m}, min{jLj |1 ≤ j ≤ n}}. Let l := max{max{iKi |1 ≤
Sl
i ≤ m}, max{iLj |1 ≤ j ≤ n}}. If qLα 6= pKα , let β := γ and J := ( i=f Bi ) + a1 +
a2 + γ + δ1 + · · · + δm + 1 + · · · + n , with the extra vertices and edges embedded in a
planar way in the infinite face. If qLα = pKα , note n = 1 and let a1 = a2 , β := 1 , and
Sl
J := ( i=f Bi ) + a1 + δ1 + · · · + δm + 1 , with the extra vertex and edges embedded in a planar
way in the infinite face.
Notice J is 2-connected, and since only at most two vertices were added while V (XG ),
containing at least three vertices, was deleted, |V (J)| < |V (G)|. Thus induction gives PJ , a
bf −1 βbl -path in J. For i < f or i > l, let ζi be an edge of XBi and Pi be a bi−1 ζi bi -path in Bi .
There is exactly one integer i such that δi ∈ E(PJ ); let Kδ := Ki . There are two cases on how
to define PKδ .
Case 1. Kδ is a trivial XG , H-connector.
Let PKδ := Kδ .
Case 2. Kδ is a non-trivial XG , H-connector group.
Let η := vKδ qKδ and M := Kδ ∪ QKδ + η, with η embedded in the infinite face such that
V (QKδ ) ⊂ V (XM ). Let θ be an edge of XM containing pKδ . There are two cases on how to
define a circuit C.
Case 2a. α 6∈ E(QKδ ).
Let C be a Tutte path in M from vKδ to qKδ through θ by Lemma 1.
Case 2b. a ∈ E(QKδ ).
Let C be a Tutte circuit through α, η, θ in M by the Three Edge Lemma.
For each of Cases 2a and 2b, let PKδ := C − η.
There is exactly one integer j such that j ∈ E(PJ ); let L := Lj . There are two cases on
how to define PL .
Case 1. L is a trivial XG , H-connector.
Let PL := L .
Case 2. L is a non-trivial XG , H-connector group.
Case 2a. qLα 6= pKα .
Let ι := vL pL , and Na := L ∪ QL + ι, with ι embedded in the infinite face such that
V (QLα ) ⊂ V (XNα ). Let λ be an edge of XNα containing qL . Let D be the Tutte path in Na
from vL to pL through λ by Lemma 1. Let PL := D − ι.
ON PATHS IN PLANAR GRAPHS 345
Case 2b. qLα = pKα .
Let κ := vL qL and Nb := L ∪ QL + κ, with κ embedded in the infinite face such that
V (QL ) ⊂ V (XNb ). Let Pb be a pL κqL -path in Nb by induction. Let PL := vL Pb pL .
Let P be the path in XG from pL counterclockwise to qKδ . Finally, let T := PJ ∪
Sk
Sf −1 X
( i=1 Pi ) ∪ ( i=l+1 Pi ) ∪ PKδ ∪ PL ∪ PX − a1 − a2 .
Now T can be modified to become a Tutte path P in G. For a bridge A of T with
V (A) ∩ V (XG ) 6= ∅, let QA , pA , qA be defined as with XG , H-connectors. Also, let the bridges
be grouped as before.
If there is a non-trivial bridge group A of T with all its vertices of attachment in V (XG )∩V (T ),
then let µ := pA qA and M := A ∪ QA + µ, with µ embedded in the infinite face such that
V (QA ) ⊂ V (XM ). If α ∈ E(QA ), then let β := α, else let β be any edge of XM distinct from
µ. Let C be a Tutte path in M from pA to qA through β by Lemma 1. Modify T by replacing QA
by C in T.
If there is a bridge group Aα of T remaining with α ∈ E(QAα ), then let ν := vAα pAα , ξ :=
vAα qAα , N := Aα ∪ QAα + ν + ξ, with ξ embedded in the infinite face such that V (QAα ) ⊂
V (XN ). (Notice that Aα = Kα .) Let C be the Tutte circuit through α, ν, ξ in N from the Three
Edge Lemma. Modify T by replacing QAα by C − vAα in T.
Note that every bridge group of T has at most two vertices of attachment not in V (XG ). In
each case, a portion of T which is a subgraph of XG will be replaced by a path through the
corresponding bridge group.
Let R2 be a bridge group of T with two vertices of attachment not in V (XG ). Let u1 (u2 ) be
the most counterclockwise (clockwise) vertices of attachment of R2 in XG . Let U be the path
in XG from u1 clockwise to u2 . Notice U is a subgraph of T. Let v1 and v2 be the vertices of
attachment of R2 not in XG such that ui and vi are in the boundary of some face Fi of G. Let
πi := ui vi , ρ := v1 v2 , and H2 := R2 ∪ U + π1 + π2 + ρ, with π1 , π2 , ρ embedded in the infinite
face such that V (U ) ⊂ V (XH2 ). Note H2 is 2-connected and plane; thus there is a Tutte circuit
C2 through π1 , π2 , ρ by the Three Edge Lemma. Let P2 be the path from u1 to u2 in C2 not
through v1 . Now T is modified by replacing U with P2 . Repeat this process for all such R2 .
Let R1 be a bridge group of T with one vertex of attachment not in V (XG ). Let u1 (u2 ) be
the most counterclockwise (clockwise) vertices of attachment of R1 in XG . Let U be the path in
XG from u1 clockwise to u2 . Notice U is a subgraph of T. Let t be the vertex of attachment of
R1 not in XG . Let σi := ui t and H1 := R1 ∪ U + σ1 + σ2 , with σ1 , σ2 embedded in the infinite
face such that V (U ) ⊂ V (XH1 ). Note H1 is 2-connected and plane; thus there is a Tutte path P1
from u1 to t through σ2 by Lemma 1. Now T is modified by replacing U with u1 P1 u2 . Repeat
this process for all such R1 .
References
[1]
N. Chiba and T. Nishizeki, A theorem on planar graphs, J. Graph Theory 10 (1986), 449–450.
[2]
D. P. Sanders, On Hamiltonian cycles in certain planar graphs, J. Graph Theory 21 (1996), 43–50.
[3]
R. Thomas and X. Yu, 4-Connected projective planar graphs are Hamiltonian, J. Combin. Theory Ser.
B 62 (1994), 114–132.
[4]
C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983), 169–176.
[5]
W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956), 99–116.
Received November 9, 1993
Документ
Категория
Без категории
Просмотров
2
Размер файла
93 Кб
Теги
281
1/--страниц
Пожаловаться на содержимое документа