On the existence of a cycle of length at least 7 in a (1,≤ 2)-twin-free graph

David Auger; Irène Charon; Olivier Hudry; Antoine Lobstein

Discussiones Mathematicae Graph Theory (2010)

  • Volume: 30, Issue: 4, page 591-609
  • ISSN: 2083-5892

Abstract

top
We consider a simple, undirected graph G. The ball of a subset Y of vertices in G is the set of vertices in G at distance at most one from a vertex in Y. Assuming that the balls of all subsets of at most two vertices in G are distinct, we prove that G admits a cycle with length at least 7.

How to cite

top

David Auger, et al. "On the existence of a cycle of length at least 7 in a (1,≤ 2)-twin-free graph." Discussiones Mathematicae Graph Theory 30.4 (2010): 591-609. <http://eudml.org/doc/270978>.

@article{DavidAuger2010,
abstract = {We consider a simple, undirected graph G. The ball of a subset Y of vertices in G is the set of vertices in G at distance at most one from a vertex in Y. Assuming that the balls of all subsets of at most two vertices in G are distinct, we prove that G admits a cycle with length at least 7.},
author = {David Auger, Irène Charon, Olivier Hudry, Antoine Lobstein},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {undirected graph; twin subsets; identifiable graph; distinguishable graph; identifying code; maximum length cycle},
language = {eng},
number = {4},
pages = {591-609},
title = {On the existence of a cycle of length at least 7 in a (1,≤ 2)-twin-free graph},
url = {http://eudml.org/doc/270978},
volume = {30},
year = {2010},
}

TY - JOUR
AU - David Auger
AU - Irène Charon
AU - Olivier Hudry
AU - Antoine Lobstein
TI - On the existence of a cycle of length at least 7 in a (1,≤ 2)-twin-free graph
JO - Discussiones Mathematicae Graph Theory
PY - 2010
VL - 30
IS - 4
SP - 591
EP - 609
AB - We consider a simple, undirected graph G. The ball of a subset Y of vertices in G is the set of vertices in G at distance at most one from a vertex in Y. Assuming that the balls of all subsets of at most two vertices in G are distinct, we prove that G admits a cycle with length at least 7.
LA - eng
KW - undirected graph; twin subsets; identifiable graph; distinguishable graph; identifying code; maximum length cycle
UR - http://eudml.org/doc/270978
ER -

References

top
  1. [1] D. Auger, Induced paths in twin-free graphs, Electron. J. Combinatorics 15 (2008) N17. Zbl1160.05316
  2. [2] C. Berge, Graphes (Gauthier-Villars, 1983). 
  3. [3] C. Berge, Graphs (North-Holland, 1985). 
  4. [4] I. Charon, I. Honkala, O. Hudry and A. Lobstein, Structural properties of twin-free graphs, Electron. J. Combinatorics 14 (2007) R16. Zbl1113.05085
  5. [5] I. Charon, O. Hudry and A. Lobstein, On the structure of identifiable graphs: results, conjectures, and open problems, in: Proceedings 29th Australasian Conference in Combinatorial Mathematics and Combinatorial Computing (Taupo, New Zealand, 2004) 37-38. 
  6. [6] R. Diestel, Graph Theory (Springer, 3rd edition, 2005). 
  7. [7] S. Gravier and J. Moncel, Construction of codes identifying sets of vertices, Electron. J. Combinatorics 12 (2005) R13. Zbl1060.05091
  8. [8] I. Honkala, T. Laihonen and S. Ranto, On codes identifying sets of vertices in Hamming spaces, Designs, Codes and Cryptography 24 (2001) 193-204, doi: 10.1023/A:1011256721935. Zbl1008.94028
  9. [9] T. Laihonen, On cages admitting identifying codes, European J. Combinatorics 29 (2008) 737-741, doi: 10.1016/j.ejc.2007.02.016. Zbl1143.05036
  10. [10] T. Laihonen and J. Moncel, On graphs admitting codes identifying sets of vertices, Australasian J. Combinatorics 41 (2008) 81-91. Zbl1201.05072
  11. [11] T. Laihonen and S. Ranto, Codes identifying sets of vertices, in: Lecture Notes in Computer Science, No. 2227 (Springer-Verlag, 2001) 82-91. Zbl1057.94035
  12. [12] A. Lobstein, Bibliography on identifying, locating-dominating and discriminating codes in graphs, http://www.infres.enst.fr/~lobstein/debutBIBidetlocdom.pdf. 
  13. [13] J. Moncel, Codes identifiants dans les graphes, Thèse de Doctorat, Université de Grenoble, France, 165 pages, June 2005. 

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.