Induced Cycles in Graphs

Michael A. Henning; Felix Joos; Christian Löwenstein; Thomas Sasse

doi:10.1007/s00373-016-1713-z

Induced Cycles in Graphs

Michael A. Henning, Felix Joos, Christian Löwenstein, Thomas Sasse

Mathematics and Applied Mathematics

Ulm University

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

5 Citations (Scopus)

Abstract

The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by c_ind(G). We prove that if G is an r-regular graph of order n, then cind(G)≥n2(r-1)+1(r-1)(r-2) and we prove that if G is a cubic, claw-free graph on order n, then cind(G)>1320n and this bound is asymptotically best possible.

Original language	English
Pages (from-to)	2425-2441
Number of pages	17
Journal	Graphs and Combinatorics
Volume	32
Issue number	6
DOIs	https://doi.org/10.1007/s00373-016-1713-z
Publication status	Published - 1 Nov 2016

Keywords

1-Extendability
Claw-free
Induced cycle
Induced regular subgrapha
Matching

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s00373-016-1713-z

Cite this

@article{58401d99a1fe47eda88e6a6a89faaf9c,

title = "Induced Cycles in Graphs",

abstract = "The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by cind(G). We prove that if G is an r-regular graph of order n, then cind(G)≥n2(r-1)+1(r-1)(r-2) and we prove that if G is a cubic, claw-free graph on order n, then cind(G)>1320n and this bound is asymptotically best possible.",

keywords = "1-Extendability, Claw-free, Induced cycle, Induced regular subgrapha, Matching",

author = "Henning, {Michael A.} and Felix Joos and Christian L{\"o}wenstein and Thomas Sasse",

note = "Publisher Copyright: {\textcopyright} 2016, Springer Japan.",

year = "2016",

month = nov,

day = "1",

doi = "10.1007/s00373-016-1713-z",

language = "English",

volume = "32",

pages = "2425--2441",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "6",

}

TY - JOUR

T1 - Induced Cycles in Graphs

AU - Henning, Michael A.

AU - Joos, Felix

AU - Löwenstein, Christian

AU - Sasse, Thomas

PY - 2016/11/1

Y1 - 2016/11/1

N2 - The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by cind(G). We prove that if G is an r-regular graph of order n, then cind(G)≥n2(r-1)+1(r-1)(r-2) and we prove that if G is a cubic, claw-free graph on order n, then cind(G)>1320n and this bound is asymptotically best possible.

AB - The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by cind(G). We prove that if G is an r-regular graph of order n, then cind(G)≥n2(r-1)+1(r-1)(r-2) and we prove that if G is a cubic, claw-free graph on order n, then cind(G)>1320n and this bound is asymptotically best possible.

KW - 1-Extendability

KW - Claw-free

KW - Induced cycle

KW - Induced regular subgrapha

KW - Matching

UR - http://www.scopus.com/inward/record.url?scp=84976321339&partnerID=8YFLogxK

U2 - 10.1007/s00373-016-1713-z

DO - 10.1007/s00373-016-1713-z

M3 - Article

AN - SCOPUS:84976321339

SN - 0911-0119

VL - 32

SP - 2425

EP - 2441

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 6

ER -

Induced Cycles in Graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this