The bondage numbers of graphs with small crossing numbers

Jia Huang; Jun Ming Xu

doi:10.1016/j.disc.2006.09.035

The bondage numbers of graphs with small crossing numbers

Jia Huang, Jun Ming Xu

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

5 Scopus citations

Abstract

The bondage number b (G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ (G) of G. Kang and Yuan proved b (G) ≤ 8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers.

Original language	English (US)
Pages (from-to)	1881-1897
Number of pages	17
Journal	Discrete Mathematics
Volume	307
Issue number	15
DOIs	https://doi.org/10.1016/j.disc.2006.09.035
State	Published - Jul 6 2007
Externally published	Yes

Keywords

Bondage number
Crossing number
Domination number
Planar graph

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2006.09.035

Cite this

@article{4ffd3d01fe034ef3ba7f6060c7ed5ee6,

title = "The bondage numbers of graphs with small crossing numbers",

abstract = "The bondage number b (G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ (G) of G. Kang and Yuan proved b (G) ≤ 8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers.",

keywords = "Bondage number, Crossing number, Domination number, Planar graph",

author = "Jia Huang and Xu, {Jun Ming}",

note = "Funding Information: The work was supported by NNSF of China (No. 10671191). ",

year = "2007",

month = jul,

day = "6",

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

language = "English (US)",

volume = "307",

pages = "1881--1897",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "15",

}

TY - JOUR

T1 - The bondage numbers of graphs with small crossing numbers

AU - Huang, Jia

AU - Xu, Jun Ming

N1 - Funding Information: The work was supported by NNSF of China (No. 10671191).

PY - 2007/7/6

Y1 - 2007/7/6

N2 - The bondage number b (G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ (G) of G. Kang and Yuan proved b (G) ≤ 8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers.

AB - The bondage number b (G) of a nonempty graph G is the cardinality of a smallest edge set whose removal from G results in a graph with domination number greater than the domination number γ (G) of G. Kang and Yuan proved b (G) ≤ 8 for every connected planar graph G. Fischermann, Rautenbach and Volkmann obtained some further results for connected planar graphs. In this paper, we generalize their results to connected graphs with small crossing numbers.

KW - Bondage number

KW - Crossing number

KW - Domination number

KW - Planar graph

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

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

U2 - 10.1016/j.disc.2006.09.035

DO - 10.1016/j.disc.2006.09.035

M3 - Article

AN - SCOPUS:34247092920

SN - 0012-365X

VL - 307

SP - 1881

EP - 1897

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 15

ER -

The bondage numbers of graphs with small crossing numbers

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this