On certain spanning subgraphs of embeddings with applications to domination

DOI10.1016/j.disc.2008.06.010zbMath1221.05094OpenAlexW2090589639MaRDI QIDQ1044949

Michael D. Plummer, Xiaoya Zha

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

surfacetriangulationembeddingtorusKlein bottledominating setdomination numberrepresentativityspanning subset

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (8)

Dominating plane triangulations ⋮ Bounds for the connected domination number of maximal outerplanar graphs ⋮ The domination number of plane triangulations ⋮ Dominating maximal outerplane graphs and Hamiltonian plane triangulations ⋮ A note on vertices contained in the minimum dominating set of a graph with minimum degree three ⋮ Dominating sets in triangulations on surfaces ⋮ Achromatic number and facial achromatic number of connected locally-connected graphs ⋮ A Note on the Domination Number of Triangulations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 2-connected spanning subgraphs with low maximum degree in locally planar graphs
• A note on the k-domination number of a graph
• An upper bound on the domination number of \(n\)-vertex connected cubic graphs
• Five-coloring maps on surfaces
• Trees in triangulations
• Graphs on the torus and geometry of numbers
• Subgraphs of graphs on surfaces with high representativity
• Long cycles in graphs on a fixed surface
• A theorem on paths in locally planar triangulations
• Spanning planar subgraphs of graphs in the torus and Klein bottle
• Dominating sets in planar graphs
• On the matching extendability of graphs in surfaces
• Domination in graphs of minimum degree at least two and large girth
• Domination in graphs of minimum degree five
• On domination in connected cubic graphs
• Disjoint paths, planarizing cycles, and spanning walks
• Domination in graphs with minimum degree two
• Bounds on a generalized domination parameter
• On the orientable genus of graphs embedded in the klein bottle
• Paths, Stars and the Number Three
• 2-connected 7-coverings of 3-connected graphs on surfaces
• The dominating number of a random cubic graph
• Computing the orientable genus of projective graphs
• 2‐connected coverings of bounded degree in 3‐connected graphs
• Domination in a graph with a 2‐factor

This page was built for publication: On certain spanning subgraphs of embeddings with applications to domination