Splitting Cubic Circle Graphs

Lorenzo Traldi

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 723-741
  • ISSN: 2083-5892

Abstract

top
We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition. We also deduce that up to isomorphism, K4 and K3,3 are the only 3-connected, 3-regular circle graphs.

How to cite

top

Lorenzo Traldi. "Splitting Cubic Circle Graphs." Discussiones Mathematicae Graph Theory 36.3 (2016): 723-741. <http://eudml.org/doc/285467>.

@article{LorenzoTraldi2016,
abstract = {We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition. We also deduce that up to isomorphism, K4 and K3,3 are the only 3-connected, 3-regular circle graphs.},
author = {Lorenzo Traldi},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {circle graph; split decomposition; regular graph},
language = {eng},
number = {3},
pages = {723-741},
title = {Splitting Cubic Circle Graphs},
url = {http://eudml.org/doc/285467},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Lorenzo Traldi
TI - Splitting Cubic Circle Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 723
EP - 741
AB - We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition. We also deduce that up to isomorphism, K4 and K3,3 are the only 3-connected, 3-regular circle graphs.
LA - eng
KW - circle graph; split decomposition; regular graph
UR - http://eudml.org/doc/285467
ER -

References

top
  1. [1] F. Bonomo, G. Durán, L.N. Grippo and M.D. Safe, Partial characterizations of circle graphs, Discrete Appl. Math. 159 (2011) 1699-1706. doi:10.1016/j.dam.2010.06.020[Crossref][WoS] Zbl1228.05243
  2. [2] A. Bouchet, Caractérisation des symboles croisés de genre nul , C.R. Acad. Sci. Paris Śer. A-B 274 (1972) A724-A727. Zbl0228.05104
  3. [3] A. Bouchet, Reducing prime graphs and recognizing circle graphs, Combinatorica 7 (1987) 243-254. doi:10.1007/BF02579301[Crossref] Zbl0666.05037
  4. [4] A. Bouchet, Circle graph obstructions, J. Combin. Theory Ser. B 60 (1994) 107-144. doi:10.1006/jctb.1994.1008[Crossref] Zbl0793.05116
  5. [5] H.R. Brahana, Systems of circuits on two-dimensional manifolds, Ann. of Math. 23 (1921) 144-168. doi:10.2307/1968030[Crossref] Zbl48.0661.02
  6. [6] M. Cohn and A. Lempel, Cycle decomposition by disjoint transpositions, J. Combin. Theory Ser. A 13 (1972) 83-89. doi:10.1016/0097-3165(72)90010-6[Crossref] Zbl0314.05005
  7. [7] B. Courcelle, Circle graphs and monadic second-order logic, J. Appl. Log. 6 (2008) 416-442. doi:10.1016/j.jal.2007.05.001[Crossref] Zbl1149.03011
  8. [8] W.H. Cunningham, Decomposition of directed graphs, SIAM J. Alg. Disc. Meth. 3 (1982) 214-228. doi:10.1137/0603021[Crossref] Zbl0497.05031
  9. [9] J. Daligault, D. Gonçalves and M. Rao, Diamond-free circle graphs are Helly circle, Discrete Math. 310 (2010) 845-849. doi:10.1016/j.disc.2009.09.022[WoS][Crossref] Zbl1222.05033
  10. [10] S. Even and A. Itai, Queues, stacks, and graphs, in: Theory of Machines and Computations, Proc. Internat. Sympos., Technion, Haifa, 1971, Z. Kohavi and A. Paz (Ed(s)), (Academic Press, New York, 1971) 71-86. doi:10.1016/b978-0-12-417750-5.50011-7[Crossref] 
  11. [11] L. Ghier, Double occurrence words with the same alternance graph, Ars Combin. 36 (1993) 57-64. Zbl0793.05124
  12. [12] E. Gioan, C. Paul, M. Tedder and D. Corneil, Practical and efficient circle graph recognition, Algorithmica 69 (2014) 759-788. doi:10.1007/s00453-013-9745-8[WoS][Crossref] Zbl1303.05190
  13. [13] E. Gioan, C. Paul, M. Tedder and D. Corneil, Practical and efficient split decompo- sition via graph-labelled trees, Algorithmica 69 (2014) 789-843. doi:10.1007/s00453-013-9752-9[WoS][Crossref] Zbl1303.05191
  14. [14] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). Zbl0541.05054
  15. [15] A. Kotzig, Eulerian lines in finite 4-valent graphs and their transformations, in: Theory of Graphs, Proc. Colloq., Tihany, 1966, P. Erdős and G. Katona (Ed(s)), (Academic Press, New York, 1968) 219-230. 
  16. [16] W. Naji, Reconnaissance des graphes de cordes, Discrete Math. 54 (1985) 329-337. doi:10.1016/0012-365X(85)90117-7[Crossref] Zbl0567.05033
  17. [17] R.C. Read and P. Rosenstiehl, On the Gauss crossing problem, in: Combina- torics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai, 18, A. Hajnal and V.T. Śos (Ed(s)), (North-Holland Publishing Co., Amsterdam-New York, 1978) 843-876. 
  18. [18] J. Spinrad, Recognition of circle graphs, J. Algorithms 16 (1994) 264-282. doi:10.1006/jagm.1994.1012[Crossref] Zbl0797.68130
  19. [19] B. Zelinka, The graph of the system of chords of a given circle, Mat.-Fyz. Časopis Sloven. Akad. Vied 15 (1965) 273-279. Zbl0142.41601

NotesEmbed ?

top

You must be logged in to post comments.