Independent bondage number of planar graphs with minimum degree at least 3

DOI10.1016/J.DISC.2022.113072MaRDI QIDQ2675833zbMATH OpenOpenAlexWikidataFDO

Authors Andrew Pham, Bing Wei

Publication date 26 September 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2022.113072

zbMATH Keywords

independent bondage numberindependent domination

Mathematics Subject Classification ID

Vertex degrees (05C07) Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

Let \(G=(V,E)\) be a simple graph. A dominating set of \(G\) is a subset \(D\subseteq V\) such that every vertex not in \(D\) is adjacent to at least one vertex in \(D\). Additionally, if \(D\) is independent as well, we say \(D\) is an independent dominating set. The cardinality of the smallest independent dominating set of \(G\), denoted by \(\gamma_i(G)\), is the independent domination number of \(G\). The independent bondage number of \(G\) is denoted by \(b_i(G)\) and is the minimum number of edges whose removal changes the independent domination number. Domination number and bondage number have been an active research topic in the past few decades. Independent bondage is a newer concept and has few results about it. The authors in this paper have shown that for planar graphs with minimum degree \(\delta(G)\geq 3\), we have \(b_i(G)\leq 9\). Also, they constructed a class of planar graphs with \(b_i(G)=6\).

Recommendations

• Independent bondage number of a graph
• Bondage number of planar graphs
• Remarks on the bondage number of planar graphs
• Bondage number of planar graphs without small cycles
• scientific article; zbMATH DE number 825127

Cites work

• All tight descriptions of 3-paths centered at 2-vertices in plane graphs with girth at least 6
• An introduction to the discharging method via graph coloring
• Bondage number of planar graphs
• Bounds on the bondage number of a graph
• Colorings of plane graphs: a survey
• Independent bondage number of a graph
• On bondage numbers of graphs: a survey with some comments

Cited in

(5)

• Bondage number of planar graphs
• Independent bondage number of a graph
• Planar graphs have independence ratio at least 3/13
• Independent k -rainbow bondage number of graphs
• An upper bound on the independent domination number of k-trees

This page was built for publication: Independent bondage number of planar graphs with minimum degree at least 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2675833)