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

David Auger; Iŕene Charon; Olivier Hudry; Antoine Lobstein

doi:10.7151/dmgt.1516

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

David Auger
, Iŕene Charon
, Olivier Hudry
, Antoine Lobstein

CNRS

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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.

langue originale	Anglais
Pages (de - à)	591-609
Nombre de pages	19
journal	Discussiones Mathematicae - Graph Theory
Volume	30
Numéro de publication	4
Les DOIs	https://doi.org/10.7151/dmgt.1516
état	Publié - 1 janv. 2010

Accès au document

10.7151/dmgt.1516

Contient cette citation

@article{460b53bd3cb84331b7df25623c062eb0,

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

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 = "Distin-guishable graph, Identiable graph, Identifying code, Maximum length cycle, Twin subsets, Undirected graph",

author = "David Auger and I{\'r}ene Charon and Olivier Hudry and Antoine Lobstein",

year = "2010",

month = jan,

day = "1",

doi = "10.7151/dmgt.1516",

language = "English",

volume = "30",

pages = "591--609",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "4",

}

TY - JOUR

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

AU - Auger, David

AU - Charon, Iŕene

AU - Hudry, Olivier

AU - Lobstein, Antoine

PY - 2010/1/1

Y1 - 2010/1/1

N2 - 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.

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.

KW - Distin-guishable graph

KW - Identiable graph

KW - Identifying code

KW - Maximum length cycle

KW - Twin subsets

KW - Undirected graph

U2 - 10.7151/dmgt.1516

DO - 10.7151/dmgt.1516

M3 - Article

AN - SCOPUS:78649954036

SN - 1234-3099

VL - 30

SP - 591

EP - 609

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 4

ER -

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

Résumé

Accès au document

Empreinte digitale

Contient cette citation