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

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

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	American English
Journal	Scholarship and Professional Work - LAS
Volume	309
Issue number	10
DOIs	https://doi.org/10.1016/j.disc.2008.09.014
State	Published - Jan 1 2009

Keywords

Computer Science
collapsible graphs
reduction

Disciplines

Computer Sciences
Mathematics

Access to Document

10.1016/j.disc.2008.09.014License: Unspecified

Collapsible graphs and reductions of line graphsFinal published version, 971 KBLicense: Unspecified

Cite this

@article{8c4a1e0fffec4436b7fd6dd162587141,

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 = "Computer Science, collapsible graphs, reduction",

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

year = "2009",

month = jan,

day = "1",

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

language = "American English",

volume = "309",

journal = "Scholarship and Professional Work - LAS",

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/1/1

Y1 - 2009/1/1

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 - Computer Science

KW - collapsible graphs

KW - reduction

UR - https://digitalcommons.butler.edu/facsch_papers/141

U2 - 10.1016/j.disc.2008.09.014

DO - 10.1016/j.disc.2008.09.014

M3 - Article

VL - 309

JO - Scholarship and Professional Work - LAS

JF - Scholarship and Professional Work - LAS

IS - 10

ER -

Collapsible graphs and reductions of line graphs

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this