Upper bounds for domination related parameters in graphs on surfaces

DOI10.1016/J.AKCEJ.2016.06.007MaRDI QIDQ334124zbMATH OpenOpenAlexFDO

Authors Vladimir Samodivkin

Publication date 31 October 2016

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1310.1610

zbMATH Keywords

Euler characteristicnonorientable genusorientable genusRoman bondage numbertotal connected domination numbertotal restrained bondage numberweakly connected domination number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07) Connectivity (05C40)

Abstract: In this paper we give tight upper bounds on the total domination number, the weakly connected domination number and the connected domination number of a graph in terms of order and Euler characteristic. We also present upper bounds for the restrained bondage number, the total restrained bondage number and the restricted edge connectivity of graphs in terms of the orientable/nonorientable genus and maximum degree.

Recommendations

• Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces.
• Upper bounds for the bondage number of graphs on topological surfaces
• An improved upper bound for the bondage number of graphs on surfaces
• New upper bounds for the bondage number of a graph in terms of its maximum degree and Euler characteristic.
• Maximum sizes of graphs with given domination parameters

Cites work

• scientific article; zbMATH DE number 4047749 (Why is no real title available?)
• scientific article; zbMATH DE number 3179262 (Why is no real title available?)
• scientific article; zbMATH DE number 125461 (Why is no real title available?)
• scientific article; zbMATH DE number 3450230 (Why is no real title available?)
• A Characterization in of Upper-Embeddable Graphs
• A Kotzig type theorem for non-orientable surfaces
• A bound on the size of a graph with given order and bondage number
• A note on the Roman bondage number of planar graphs
• Describing 3-paths in normal plane maps
• Generalized Embedding Schemes
• Note on the bondage number of graphs on topological surfaces
• On bondage numbers of graphs: a survey with some comments
• On computing a conditional edge-connectivity of a graph
• On the Roman bondage number of planar graphs
• On the number of edges in graphs with a given connected domination number
• On the number of edges in graphs with a given weakly connected domination number
• On weakly connected domination in graphs
• Relating the size of a connected graph to its total and restricted domination numbers
• Restrained bondage in graphs
• Total restrained bondage in graphs
• Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces.

Cited in

(5)

• scientific article; zbMATH DE number 1529469 (Why is no real title available?)
• An improved upper bound for the bondage number of graphs on surfaces
• Upper bounds on the maximum degree of class two graphs on surfaces
• Roman domination in graphs
• Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces.

This page was built for publication: Upper bounds for domination related parameters in graphs on surfaces

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