Upper bounds for domination related parameters in graphs on surfaces

DOI10.1016/J.AKCEJ.2016.06.007zbMATH Open1348.05155arXiv1310.1610OpenAlexW1761046967MaRDI QIDQ334124FDOQ334124

Vladimir Samodivkin

Publication date: 31 October 2016

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

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.

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

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

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)

Cites Work

• Describing 3-paths in normal plane maps
• Title not available (Why is that?)
• On computing a conditional edge-connectivity of a graph
• On bondage numbers of graphs: a survey with some comments
• On the number of edges in graphs with a given connected domination number
• Title not available (Why is that?)
• Title not available (Why is that?)
• A bound on the size of a graph with given order and bondage number
• On weakly connected domination in graphs
• Relating the size of a connected graph to its total and restricted domination numbers
• On the number of edges in graphs with a given weakly connected domination number
• A note on the Roman bondage number of planar graphs
• Total restrained bondage in graphs
• Note on the bondage number of graphs on topological surfaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Characterization in of Upper-Embeddable Graphs
• Generalized Embedding Schemes
• Upper bounds for the domination subdivision and bondage numbers of graphs on topological surfaces
• On the Roman bondage number of planar graphs
• Restrained bondage in graphs

Cited In (3)

• Roman Domination in Graphs
• Title not available (Why is that?)
• Upper bounds on the maximum degree of class two graphs on 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)