Geodesic
Split Euler Tours In 4-Regular Planar Graphs
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 23-30

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: 4-regular, 3-connected, planar, split Euler tour, NP-complete 
@article{DMGT_2016_36_1_a1,
     author = {Couch, PJ and Daniel, B.D. and Guidry, R. and Paul Wright, W.},
     title = {Split {Euler} {Tours} {In} {4-Regular} {Planar} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {23--30},
     publisher = {mathdoc},
     volume = {36},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a1/}
}
TY  - JOUR
AU  - Couch, PJ
AU  - Daniel, B.D.
AU  - Guidry, R.
AU  - Paul Wright, W.
TI  - Split Euler Tours In 4-Regular Planar Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 23
EP  - 30
VL  - 36
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a1/
LA  - en
ID  - DMGT_2016_36_1_a1
ER  - 
%0 Journal Article
%A Couch, PJ
%A Daniel, B.D.
%A Guidry, R.
%A Paul Wright, W.
%T Split Euler Tours In 4-Regular Planar Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 23-30
%V 36
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a1/
%G en
%F DMGT_2016_36_1_a1
Couch, PJ; Daniel, B.D.; Guidry, R.; Paul Wright, W. Split Euler Tours In 4-Regular Planar Graphs. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 1, pp. 23-30. http://geodesic.mathdoc.fr/item/DMGT_2016_36_1_a1/