Split Euler Tours In 4-Regular Planar Graphs

PJ Couch; B.D. Daniel; R. Guidry; W. Paul Wright

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 1, page 23-30
  • ISSN: 2083-5892

Abstract

top
The construction of a homing tour is known to be NP-complete. On the other hand, the Euler formula puts su cient restrictions on plane graphs that one should be able to assert the existence of such tours in some cases; in particular we focus on split Euler tours (SETs) in 3-connected, 4-regular, planar graphs (tfps). An Euler tour S in a graph G is a SET if there is a vertex v (called a half vertex of S) such that the longest portion of the tour between successive visits to v is exactly half the number of edges of G. Among other results, we establish that every tfp G having a SET S in which every vertex of G is a half vertex of S can be transformed to another tfp G′ having a SET S′ in which every vertex of G′ is a half vertex of S′ and G′ has at most one point having a face configuration of a particular class. The various results rely heavily on the structure of such graphs as determined by the Euler formula and on the construction of tfps from the octahedron. We also construct a 2-connected 4-regular planar graph that does not have a SET.

How to cite

top

PJ Couch, et al. "Split Euler Tours In 4-Regular Planar Graphs." Discussiones Mathematicae Graph Theory 36.1 (2016): 23-30. <http://eudml.org/doc/276977>.

@article{PJCouch2016,
abstract = {The construction of a homing tour is known to be NP-complete. On the other hand, the Euler formula puts su cient restrictions on plane graphs that one should be able to assert the existence of such tours in some cases; in particular we focus on split Euler tours (SETs) in 3-connected, 4-regular, planar graphs (tfps). An Euler tour S in a graph G is a SET if there is a vertex v (called a half vertex of S) such that the longest portion of the tour between successive visits to v is exactly half the number of edges of G. Among other results, we establish that every tfp G having a SET S in which every vertex of G is a half vertex of S can be transformed to another tfp G′ having a SET S′ in which every vertex of G′ is a half vertex of S′ and G′ has at most one point having a face configuration of a particular class. The various results rely heavily on the structure of such graphs as determined by the Euler formula and on the construction of tfps from the octahedron. We also construct a 2-connected 4-regular planar graph that does not have a SET.},
author = {PJ Couch, B.D. Daniel, R. Guidry, W. Paul Wright},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {4-regular; 3-connected; planar; split Euler tour; NP-complete},
language = {eng},
number = {1},
pages = {23-30},
title = {Split Euler Tours In 4-Regular Planar Graphs},
url = {http://eudml.org/doc/276977},
volume = {36},
year = {2016},
}

TY - JOUR
AU - PJ Couch
AU - B.D. Daniel
AU - R. Guidry
AU - W. Paul Wright
TI - Split Euler Tours In 4-Regular Planar Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 1
SP - 23
EP - 30
AB - The construction of a homing tour is known to be NP-complete. On the other hand, the Euler formula puts su cient restrictions on plane graphs that one should be able to assert the existence of such tours in some cases; in particular we focus on split Euler tours (SETs) in 3-connected, 4-regular, planar graphs (tfps). An Euler tour S in a graph G is a SET if there is a vertex v (called a half vertex of S) such that the longest portion of the tour between successive visits to v is exactly half the number of edges of G. Among other results, we establish that every tfp G having a SET S in which every vertex of G is a half vertex of S can be transformed to another tfp G′ having a SET S′ in which every vertex of G′ is a half vertex of S′ and G′ has at most one point having a face configuration of a particular class. The various results rely heavily on the structure of such graphs as determined by the Euler formula and on the construction of tfps from the octahedron. We also construct a 2-connected 4-regular planar graph that does not have a SET.
LA - eng
KW - 4-regular; 3-connected; planar; split Euler tour; NP-complete
UR - http://eudml.org/doc/276977
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (American Elsevier, New York, 1976). Zbl1226.05083
  2. [2] H.J. Broersma, A.J.W. Duijvestijn and F. Gőbel, Generating all 3-connected 4-regular planar graphs from the octahedron graph, J. Graph Theory 17 (1993) 613–620. doi:10.1002/jgt.3190170508[Crossref] Zbl0781.05047
  3. [3] J. Czap and S. Jendrol’, Colouring vertices of plane graphs under restrictions given by faces, Discuss. Math. Graph Theory 29 (2009) 521–543. doi:10.7151/dmgt.1462[Crossref] Zbl1193.05065
  4. [4] N. Dean, Which graphs are pancyclic modulo k?, in: Sixth Intl. Conference on the Theory of Applications of Graphs, (Kalamazoo, Michigan, 1988) 315–326. 
  5. [5] N. Dean, L. Lesniak and A. Saito, Cycles of length 0 modulo 4 in graphs, Discrete Math. 121 (1993) 37–49. doi:10.1016/0012-365X(93)90535-2 
  6. [6] J. Froemke, J.W. Grossman and D.M. Kulkarni, Direct message delivery among processors with limited capacity, in: Graph Theory, Combinatorics, and Algorithms, Vol. 1,2, Kalamazoo, MI, (Wiley-Intersci. Publ., Wiley, New York, 1992) 467–476. Zbl0843.68086
  7. [7] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, New York, 1979). Zbl0411.68039
  8. [8] M.R. Garey, D.S. Johnson and R.E. Tarjan, The planar Hamiltonian circuit problem is NP-complete, SIAM J. Comput. 5 (1976) 704–714. doi:10.1137/0205049[Crossref] Zbl0346.05110
  9. [9] S. Jendrol’ and H.-J. Voss, Light subgraphs of graphs embedded in the plane-A survey, Discrete Math. 313 (2013) 406–421. doi:10.1016/j.disc.2012.11.007[Crossref][WoS] Zbl1259.05045
  10. [10] H. Lebesgue, Quelques consequences simple de la formula d’Euler, J. Math. Pures Appl. 9 (1940) 27–43. Zbl0024.28701
  11. [11] J. Lehel, Generating all 4-regular planar graphs from the graph of the octahedron, J. Graph Theory 5 (1981) 423–426. doi:10.1002/jgt.3190050412[Crossref] Zbl0474.05058
  12. [12] P. Manca, Generating all planar graphs regular of degree four, J. Graph Theory 3 (1979) 357–364. doi:10.1002/jgt.3190030406[Crossref] Zbl0424.05041

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.