Collapsible graphs and reductions of line graphs

Zhi Hong Chen; Peter C.B. Lam; Wai Chee Shiu

doi:10.1016/j.disc.2008.09.014

Collapsible graphs and reductions of line graphs

Zhi Hong Chen^*, Peter C.B. Lam, Wai Chee Shiu

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Journal article › peer-review

1 Citation (Scopus)

Abstract

A graph G is collapsible if for every even subset X ⊆ V (G), G has a subgraph Γ such that G - E (Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].

Original language	English
Pages (from-to)	3173-3184
Number of pages	12
Journal	Discrete Mathematics
Volume	309
Issue number	10
DOIs	https://doi.org/10.1016/j.disc.2008.09.014
Publication status	Published - 28 May 2009

Scopus Subject Areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

User-Defined Keywords

Collapsible graph
Double cycle covers
Hamiltonian index
Line graphs
Reduction of graph

Access to Document

10.1016/j.disc.2008.09.014

Cite this

@article{72d2e32d401c44e1bf44c6b151d141f5,

title = "Collapsible graphs and reductions of line graphs",

abstract = "A graph G is collapsible if for every even subset X ⊆ V (G), G has a subgraph Γ such that G - E (Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].",

keywords = "Collapsible graph, Double cycle covers, Hamiltonian index, Line graphs, Reduction of graph",

author = "Chen, {Zhi Hong} and Lam, {Peter C.B.} and Shiu, {Wai Chee}",

year = "2009",

month = may,

day = "28",

doi = "10.1016/j.disc.2008.09.014",

language = "English",

volume = "309",

pages = "3173--3184",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "10",

}

TY - JOUR

T1 - Collapsible graphs and reductions of line graphs

AU - Chen, Zhi Hong

AU - Lam, Peter C.B.

AU - Shiu, Wai Chee

PY - 2009/5/28

Y1 - 2009/5/28

N2 - A graph G is collapsible if for every even subset X ⊆ V (G), G has a subgraph Γ such that G - E (Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].

AB - A graph G is collapsible if for every even subset X ⊆ V (G), G has a subgraph Γ such that G - E (Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].

KW - Collapsible graph

KW - Double cycle covers

KW - Hamiltonian index

KW - Line graphs

KW - Reduction of graph

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

U2 - 10.1016/j.disc.2008.09.014

DO - 10.1016/j.disc.2008.09.014

M3 - Journal article

AN - SCOPUS:67349139922

SN - 0012-365X

VL - 309

SP - 3173

EP - 3184

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10

ER -

Collapsible graphs and reductions of line graphs

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this