Induced 2-regular subgraphs in k-chordal cubic graphs

Michael A. Henning; F. Joos; C. Löwenstein; D. Rautenbach

doi:10.1016/j.dam.2016.01.009

Induced 2-regular subgraphs in k-chordal cubic graphs

Michael A. Henning, F. Joos, C. Löwenstein, D. Rautenbach

Mathematics and Applied Mathematics

Ulm University

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

1 Citation (Scopus)

Abstract

We show that a cubic graph G of order n has an induced 2-regular subgraph of order at least • n−24−4k, if G has no induced cycle of length more than k,• 5n+68, if G has no induced cycle of length more than 4, and n>6, and• (14+ϵ)n, if the independence number of G is at most (38−ϵ)n.To show the second result we give a precise structural description of cubic 4-chordal graphs.

Original language	English
Pages (from-to)	73-79
Number of pages	7
Journal	Discrete Applied Mathematics
Volume	205
DOIs	https://doi.org/10.1016/j.dam.2016.01.009
Publication status	Published - 2016

Keywords

Independent set
Induced cycle
Induced matching
Induced regular subgraph

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2016.01.009

Cite this

@article{604f6a44f51e4e95964df558a1d9b16f,

title = "Induced 2-regular subgraphs in k-chordal cubic graphs",

abstract = "We show that a cubic graph G of order n has an induced 2-regular subgraph of order at least • n−24−4k, if G has no induced cycle of length more than k,• 5n+68, if G has no induced cycle of length more than 4, and n>6, and• (14+ϵ)n, if the independence number of G is at most (38−ϵ)n.To show the second result we give a precise structural description of cubic 4-chordal graphs.",

keywords = "Independent set, Induced cycle, Induced matching, Induced regular subgraph",

author = "Henning, {Michael A.} and F. Joos and C. L{\"o}wenstein and D. Rautenbach",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2016",

doi = "10.1016/j.dam.2016.01.009",

language = "English",

volume = "205",

pages = "73--79",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

}

TY - JOUR

T1 - Induced 2-regular subgraphs in k-chordal cubic graphs

AU - Henning, Michael A.

AU - Joos, F.

AU - Löwenstein, C.

AU - Rautenbach, D.

PY - 2016

Y1 - 2016

N2 - We show that a cubic graph G of order n has an induced 2-regular subgraph of order at least • n−24−4k, if G has no induced cycle of length more than k,• 5n+68, if G has no induced cycle of length more than 4, and n>6, and• (14+ϵ)n, if the independence number of G is at most (38−ϵ)n.To show the second result we give a precise structural description of cubic 4-chordal graphs.

AB - We show that a cubic graph G of order n has an induced 2-regular subgraph of order at least • n−24−4k, if G has no induced cycle of length more than k,• 5n+68, if G has no induced cycle of length more than 4, and n>6, and• (14+ϵ)n, if the independence number of G is at most (38−ϵ)n.To show the second result we give a precise structural description of cubic 4-chordal graphs.

KW - Independent set

KW - Induced cycle

KW - Induced matching

KW - Induced regular subgraph

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

U2 - 10.1016/j.dam.2016.01.009

DO - 10.1016/j.dam.2016.01.009

M3 - Article

AN - SCOPUS:84957625633

SN - 0166-218X

VL - 205

SP - 73

EP - 79

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Induced 2-regular subgraphs in k-chordal cubic graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this