> /20@ 'jbjbܡܡ "'
lo,......,Y yZZF,,,,N0R,,oo,%%,Longest Paths in Polyhedral Graphs
------------------------------------------------------------------------
A finite graph G is called polyhedral iff it is isomorphic to the graph of vertices and edges of a 3-dimensional convex polyhedron. A graph-theoretic characterization of these graphs is given by a famous theorem due to E. Steinitz: polyhedral graphs coincide with 3-connected planar graphs. An old question concerning polyhedral graphs concerns the estimate for the minimum of the maximal length of a simple circuit in a polyhedral graph G with v = v(G) vertices. Denoting by h = h(G) the maximal length, Moon and Moser [MM] showed that h is at most c v^s where s = log 2 / log 3 = 0.630930 ... and c is a suitable constant. The graphs used to show this are easily constructed: Start with any triangle-faced polyhedron, and construct a sequence of polyhedra in which each member is obtained from the preceding one by attaching suitable shallow pyramids on all the faces. An easy calculation shows that the given estimate for s is best possible for all polyhedra in this sequence, regardless of the choice of the starting polyhedron.
One challenging open problem is to decide the validity of the following.
Conjecture: There exists a positive constant c such that every polyhedral graph with v vertices has a circuit of length at least c v^s with s = log 2 / log 3.
This is a modification of a conjecture posed explicitly in [GW], but probably conjectured by many other people as well. From private communications I know that some 20 years ago this problem attracted the attention of several rather clever people; no publication ensued since no worthwhile results were obtained.
The gap between the known and the conjectured is best seen from the fact that the existing estimates for the length of circuits involve log v rather than a power of v.
There is no clear indication what the largest c in the conjecture should be. An example shows that c < 2.203....
[[Note by Dan Archdeacon, I have heard that a paper by Z. Gao and X. Yu gives a path of length v^{.4}. F. Chung may have gotten v^{.5}, but that paper might have an error. I do not have these references.]]
References:
[GW] B. Grunbaum and H. Walther, Shortness exponents of families of graphs, J. Combinat. Theory A 14 (1973) 364-385.
[MM] J.W. Moon and L. Moser, Simple paths on polyhedra, Pacific J. Math. 13 (1963) 629-631.
------------------------------------------------------------------------
Submitted by: Branko Grunbaum
Send comments to dan.archdeacon@uvm.edu and to grunbaum@math.washington.edu
August, 1995
l#$*3IQ
AHL%
*
B
C
t
u
8>@PQS&'CJ6B*OJQJph5B*OJQJph6B*OJQJphB*OJQJph5B*CJOJQJph9$mv
w
abE
F
de'$mv
w
abE
F
de'/ =!"#$%
i(@(NormalCJmH <A@<Default Paragraph Font'
"!z'
'''DG)
.0MO
P Q c
!
)
::::::Branko GrnbaumAMacintosh HD:Users:grunbaum:Desktop:Longest Paths in Polyh Graphs@&
&
Saa&
&
n'
0@GTimes New Roman5Symbol3Arial3Times"qh;A>0=#Longest Paths in Polyhedral Graphs Branko GrnbaumBranko Grnbaum
Oh+'0
<H
T`hpx'$Longest Paths in Polyhedral Graphs ongBranko GrnbaumranNormalGBranko Grnbaum1anMicrosoft Word 10.1@G@Bw@Ⱦ
՜.+,0`hpx
'
$Longest Paths in Polyhedral Graphs Title
!#$%&'(),Root Entry FО<.1TableWordDocument"SummaryInformation(DocumentSummaryInformation8"CompObjXObjectPoolО<О< FMicrosoft Word DocumentNB6WWord.Document.8Root Entry F(|>31TableWordDocumentbbSummaryInformation(146789:;<=>?@ACDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`acdefghijklmnopqrsBDocumentSummaryInformation8(CompObjXObjectPoolО<О<0Table5
FMicrosoft Word DocumentNB6WWord.Document.8
՜.+,0`hpx
'9
!
$Longest Paths in Polyhedral Graphs Title
Oh+'0 (
DP\
ht|'$Longest Paths in Polyhedral Graphs ongBranko GrnbaumranNormalGBranko Grnbaum2anMicrosoft Word 10.1@@ԋ@Bw@k
i(@(NormalCJmH <A@<Default Paragraph Font&b!z!z z z'
0&$mvwabEF d e
'
=
>
j
b Y+w&|}*+^u01 A!!P""##$%o%%_&&&&!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!u'
=
>
j
b Y+w&|}*+^u01 A!!P""##$%o%%_&&&&000000000000000000000000000000000000000000000000000000000000000000["7X[./0'UnknownBranko GrnbaumDG>
A
C
K
Y
a
X
_
h
n
syikz?O +0EJLQ\egn`cps|9<FIdr$)4:~MSHO : ? K P """"""B#H####$-$<$H$N$$$$$ %%0%6%x%%%%%&|&&&.0MO
P Q c
!
5
;
C
L
j
a
e
p
lp-/CN29Y_T(.3 q"s"&:::::::::::::::::::::::::::::::::Branko GrnbaumAMacintosh HD:Users:grunbaum:Desktop:Longest Paths in Polyh GraphsBranko GrnbaumYMacintosh HD:Users:grunbaum:Documents:Microsoft User Data:AutoRecovery save of Longest Pa@
S
nFGOJPJQJmH $&
'
<
=
YA!&&0@0"1 "0J"0L"0#0#0$1$)0R)0T)0V)0X)0Z)0,0t31505060617070TP0L @GTimes New Roman5Symbol3Arial3Times"1h;MB
94!=#Longest Paths in Polyhedral Graphs Branko GrnbaumBranko Grnbaum
Review in linked PDF Add citation to clipboard Document Delivery Service Journal Original Article More links More links
References: 0 Reference Citations: 2 Review Citations: 1
The circumference of a graph $G$ is the length of a longest cycle in $G$. The authors show that if $G$ is a 3-connected graph embeddable in the plane, the projective plane, the torus or the Klein bottle, then $G$ has circumference at least $(1/6)|V(G)|^{0.4}+1$.
The argument is based in particular on some basic properties of convex programming; it improves a result due to B. Jackson and N. C. Wormald \ref[J. Combin. Theory Ser. B 54 (1992), no. 2, 291--321; MR 92m:05112].
Reviewed by D. de Werra
MR1926309 (2003h:05120)
Sheppardson, Laura(1-GAIT); Yu, Xingxing(1-GAIT)
Long cycles in 3-connected graphs in orientable surfaces. (English. English summary)
J. Graph Theory 41 (2002), no. 2, 69--84.
05C38 (05C10 05C40 57M15)
Review in linked PDF Add citation to clipboard Document Delivery Service Journal Original Article More links More links
References: 0 Reference Citations: 0 Review Citations: 0
G. Chen and X. Yu \ref[J. Combin. Theory Ser. B 86 (2002), no. 1, 80--99; MR 2003g:05077] recently proved the long-standing conjecture of Moon and Moser, that there is a constant $c$ such that every 3-connected planar graph on $n$ vertices has a cycle of length at least $cn^{\log_3(2)}$. The article under review applies standard surgical techniques to prove there is a constant $c$ such that, for the orientable surface $\Sigma_g$ of genus $g$, there is a constant $f(g)$ such that, if $G$ is a 3-connected graph on $n$ vertices embedded in $\Sigma_g$ with face-width at least $f(g)$, then $G$ has a cycle of length at least $cn^{\log_3(2)}$. That $c$ does not also depend on $g$ is interesting and a little surprising. [The face-width (or representativity) of an embedded graph is the smallest number of crossings with the graph over all noncontractible closed curves in the surface.]
A related article by T. Bhme, B. Mohar and C. Thomassen \ref[J. Combin. Theory Ser. B 85 (2002), no. 2, 338--347 MR1912972 ] shows that there is a number $c(g)$ such that every 3-connected graph $G$ with $n$ vertices and embedded in $\Sigma_g$ has a cycle of length at least $c(g)n^{\log_3(2)}$.
Reviewed by R. Bruce Richter
MR1912972 (Review)
Bhme, Thomas(D-ILTU-IM); Mohar, Bojan(SV-LJUB); Thomassen, Carsten(DK-TUD)
Long cycles in graphs on a fixed surface. (English. English summary)
J. Combin. Theory Ser. B 85 (2002), no. 2, 338--347.
05C38 (05C10)
References: 24 [-] Review Citations: 1
Summary: "We prove that there exists a function $a\colon{\Bbb N}_0\times{\Bbb R}_+\to\Bbb N$ such that: (i) If $G$ is a 4-connected graph of order $n$ embedded on a surface of Euler genus $g$ such that the face-width of $G$ is at least $a(g,\epsilon)$, then $G$ can be covered by two cycles each of which has length at least $(1-\epsilon)n$.
"We apply this to derive lower bounds for the length of a longest cycle in a graph $G$ on any fixed surface. Specifically, there exist functions $b\colon{\Bbb N}_0\to\Bbb N$ and $c\colon{\Bbb N}_0\to{\Bbb R}_+$ such that for every graph $G$ on $n$ vertices that is embedded on a surface of Euler genus $g$ the following statements hold: (ii) If $G$ is 4-connected, then $G$ contains a collection of at most $b(g)$ paths which cover all vertices of $G$, and $G$ contains a cycle of length at least $n/b(g)$. (iii) If $G$ is 3-connected, then $G$ contains a cycle of length at least $c(g)n^{\log2/\log3}$.
"Moreover, for each $\epsilon>0$, every 4-connected graph $G$ with sufficiently large face-width contains a spanning tree of maximum degree at most 3 and a 2-connected spanning subgraph of maximum degree at most 4 such that the number of vertices of degree 3 or 4 in either of these subgraphs is at most $\epsilon|V(G)|$."
[References]
1. D. Archdeacon, N. Hartsfield, and C. H. C. Little, Nonhamiltonian triangulations with large connectivity and representativity, J. Combin. Theory Ser. B 68 (1996), 45--55. MR1405705 (98g:57035)
2. D. W. Barnette, Trees in polyhedral graphs, Canad. J. Math. 18 (1966), 731--736. MR0195753 (33 #3951)
3. D. W. Barnette, 2-connected spanning subgraphs of planar 3-connected graphs, J. Combin. Theory Ser. B 61 (1994), 210--216. MR1280608 (95g:05064)
4. J. A. Bondy and S. C. Locke, Relative length of paths and cycles in 3-connected graphs, Discrete Math. 33 (1981), 111--122. MR0599075 (82b:05088)
5. G. Chen and X. Yu, Longest cycles in 3-connected planar graphs, submitted.
6. M. N. Ellingham and Z. Gao, Spanning trees in locally planar triangulations, J. Combin. Theory Ser. B 61 (1994), 178--198. MR1280606 (95m:05080)
7. Z. Gao, 2-connected coverings of bounded degree in 3-connected graphs, J. Graph Theory 20 (1995), 327--338. MR1355432 (96g:05048)
8. B. Grnbaum and H. Walther, Shortness exponents of families of graphs, J. Combin. Theory Ser. A 14 (1973), 364--385. MR0314691 (47 #3242)
9. Z. Gao and X. Yu, Convex programming and circumference of 3-connected graphs of low genus, J. Combin. Theory Ser. B 69 (1997), 39--51. MR1426749 (97k:90092)
10. B. Jackson and N. Wormald, Longest cycles in 3-connected planar graphs, J. Combin. Theory Ser. B 54 (1992), 291--321. MR1152454 (92m:05112)
11. K.-I. Kawarabayashi, A. Nakamoto, and K. Ota, Connected subgraphs of graphs on surfaces, preprint, 2001.
12. A. Malni\v c and B. Mohar, Generating locally cyclic triangulations of surfaces, J. Combin. Theory Ser. B 56 (1992), 147--164. MR1186752 (94b:05062)
13. B. Mohar and C. Thomassen, "Graphs on Surfaces," Johns Hopkins Press, Baltimore, 2001. MR1844449 (2002e:05050)
14. J. W. Moon and L. Moser, Simple paths on polyhedra, Pacific J. Math. 13 (1963), 629--631. MR0154276 (27 #4225)
15. N. Robertson and P. D. Seymour, Graph minors. VII. Disjoint paths on a surface, J. Combin. Theory Ser. B 45 (1988), 212--254. MR0961150 (89m:05072)
16. D. P. Sanders and Y. Zhao, On 2-connected spanning subgraphs with low maximum degree, J. Combin. Theory Ser. B 74 (1998), 64--86. MR1644055 (99h:05077)
17. R. Thomas and X. Yu, 4-connected projective planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994), 114--132. MR1290634 (95j:05133)
18. C. Thomassen, A theorem on paths in planar graphs, J. Graph Theory 7 (1983), 169--176. MR0698698 (84i:05075)
19. C. Thomassen, Embeddings of graphs with no short noncontractible cycles, J. Combin. Theory Ser. B 48 (1990), 155--177. MR1046752 (91b:05069)
20. C. Thomassen, Five-coloring maps on surfaces, J. Combin. Theory Ser. B 59 (1993), 89--105. MR1234386 (94h:05031)
21. C. Thomassen, Trees in triangulations, J. Combin. Theory Ser. B 60 (1994), 56--62. MR1256583 (95e:05039)
22. C. Thomassen, Color-critical graphs on a fixed surface, J. Combin. Theory Ser. B 70 (1997), 67--100. MR1441260 (98k:05070)
23. W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc. 82 (1956), 99--116. MR0081471 (18,408e)
24. X. Yu, Disjoint paths, planarizing cycles, and $k$-walks, Trans. Amer. Math. Soc. 349 (1997), 1333--1358. MR1401533 (97k:05132)
"r###$$h%v'x'$)T)V)X)Z)))**+,,t3566(66J77778::??B&B(BCDEFGHIJ2LVM4NjOTP>QrRSTUVWXXYZ[[/ =!"#$%@ 'jbjbܡܡb&lllllx$E,/ OCV6VVVV,,V~VQlEEVVLongest Paths in Polyhedral Graphs
------------------------------------------------------------------------
A finite graph G is called polyhedral iff it is isomorphic to the graph of vertices and edges of a 3-dimensional convex polyhedron. A graph-theoretic characterization of these graphs is given by a famous theorem due to E. Steinitz: polyhedral graphs coincide with 3-connected planar graphs. An old question concerning polyhedral graphs concerns the estimate for the minimum of the maximal length of a simple circuit in a polyhedral graph G with v = v(G) vertices. Denoting by h = h(G) the maximal length, Moon and Moser [MM] showed that h is at most c v^s where s = log 2 / log 3 = 0.630930 ... and c is a suitable constant. The graphs used to show this are easily constructed: Start with any triangle-faced polyhedron, and construct a sequence of polyhedra in which each member is obtained from the preceding one by attaching suitable shallow pyramids on all the faces. An easy calculation shows that the given estimate for s is best possible for all polyhedra in this sequence, regardless of the choice of the starting polyhedron.
One challenging open problem is to decide the validity of the following.
Conjecture: There exists a positive constant c such that every polyhedral graph with v vertices has a circuit of length at least c v^s with s = log 2 / log 3.
This is a modification of a conjecture posed explicitly in [GW], but probably conjectured by many other people as well. From private communications I know that some 20 years ago this problem attracted the attention of several rather clever people; no publication ensued since no worthwhile results were obtained.
The gap between the known and the conjectured is best seen from the fact that the existing estimates for the length of circuits involve log v rather than a power of v.
There is no clear indication what the largest c in the conjecture should be. An example shows that c < 2.203....
[[Note by Dan Archdeacon, I have heard that a paper by Z. Gao and X. Yu gives a path of length v^{.4}. F. Chung may have gotten v^{.5}, but that paper might have an error. I do not have these references.]]
References:
[GW] B. Grunbaum and H. Walther, Shortness exponents of families of graphs, J. Combinat. Theory A 14 (1973) 364-385.
[MM] J.W. Moon and L. Moser, Simple paths on polyhedra, Pacific J. Math. 13 (1963) 629-631.
------------------------------------------------------------------------
Submitted by: Branko Grunbaum
Send comments to dan.archdeacon@uvm.edu and to grunbaum@math.washington.edu
August, 1995
l#$*3IQ
AHL%
*
B
C
t
u
8>@PQS&'[CJ6B*OJQJph5B*OJQJph6B*OJQJphB*OJQJph5B*CJOJQJph:$mv
w
abE
F
de' "L"N""$mv
w
abE
F
de'/ =!"#$%
MR1426749 (97k:90092)
Gao, Zhicheng(3-CARL); Yu, Xingxing(1-GAIT)
Convex programming and circumference of $3$-connected graphs of low genus. (English. English summary)
J. Combin. Theory Ser. B 69 (1997), no. 1, 39--51.
90C35 (05C10 05C38)