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

Centre national de la recherche scientifique

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	591-609
Number of pages	19
Journal	Discussiones Mathematicae - Graph Theory
Volume	30
Issue number	4
DOIs	https://doi.org/10.7151/dmgt.1516
Publication status	Published - 1 Jan 2010

Keywords

Distin-guishable graph
Identiable graph
Identifying code
Maximum length cycle
Twin subsets
Undirected graph

Access to Document

10.7151/dmgt.1516

Cite this

@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

Abstract

Keywords

Access to Document

Fingerprint

Cite this