Download PDF - On the existence of a cycle of length at least 7 in a (1,≤ 2)-twin-free graphAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

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

Authors 1, 1, 1, 2

Affiliations

  1. Institut Telecom - Telecom ParisTech & Centre National de la Recherche Scientifique - LTCI UMR 5141, 46, rue Barrault, 75634 Paris Cedex 13, France
  2. Centre National de la Recherche Scientifique - LTCI UMR 5141 & Telecom ParisTech, 46, rue Barrault, 75634 Paris Cedex 13, France

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.

Keywords

ENG
undirected graph, twin subsets, identifiable graph, distinguishable graph, identifying code, maximum length cycle

Bibliography

  1. D. Auger, Induced paths in twin-free graphs, Electron. J. Combinatorics 15 (2008) N17.
  2. C. Berge, Graphes (Gauthier-Villars, 1983).
  3. C. Berge, Graphs (North-Holland, 1985).
  4. I. Charon, I. Honkala, O. Hudry and A. Lobstein, Structural properties of twin-free graphs, Electron. J. Combinatorics 14 (2007) R16.
  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. R. Diestel, Graph Theory (Springer, 3rd edition, 2005).
  7. S. Gravier and J. Moncel, Construction of codes identifying sets of vertices, Electron. J. Combinatorics 12 (2005) R13.
  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.
  9. T. Laihonen, On cages admitting identifying codes, European J. Combinatorics 29 (2008) 737-741, doi: 10.1016/j.ejc.2007.02.016.
  10. T. Laihonen and J. Moncel, On graphs admitting codes identifying sets of vertices, Australasian J. Combinatorics 41 (2008) 81-91.
  11. T. Laihonen and S. Ranto, Codes identifying sets of vertices, in: Lecture Notes in Computer Science, No. 2227 (Springer-Verlag, 2001) 82-91.
  12. A. Lobstein, Bibliography on identifying, locating-dominating and discriminating codes in graphs, http://www.infres.enst.fr/~lobstein/debutBIBidetlocdom.pdf.
  13. J. Moncel, Codes identifiants dans les graphes, Thèse de Doctorat, Université de Grenoble, France, 165 pages, June 2005.
Discussiones Mathematicae Graph Theory
2010/30/4
Export to PBN, Opens in new tab
Pages:
591-609
Main language of publication
English
Received
2009-07-27
Accepted
2009-12-14
Published
2010

DOI: 10.7151/dmgt.1516

Exact and natural sciences