Light subgraphs in graphs with average degree at most four

DOI10.1016/J.DISC.2016.04.020MaRDI QIDQ294570zbMATH OpenOpenAlexFDO

Authors Tao Wang

Publication date 16 June 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

average degreeplanar graphlight subgraphsnormal plane maps

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07)

Abstract: A graph $H$ is said to be {em light} in a family $mathfrakG$ of graphs if at least one member of $mathfrakG$ contains a copy of $H$ and there exists an integer $lambda(H,mathfrakG)$ such that each member $G$ of $mathfrakG$ with a copy of $H$ also has a copy $K$ of $H$ such that $de{g}_G(v)leqlambda(H,mathfrakG)$ for all $vinV(K)$. In this paper, we study the light graphs in the class of graphs with small average degree, including the plane graphs with some restrictions on girth.

Recommendations

• Light subgraphs in planar graphs of minimum degree 4 and edge‐degree 9
• On light subgraphs in plane graphs of minimum degree five
• Light graphs in planar graphs of large girth
• On light graphs in 3-connected plane graphs without triangular or quadrangular faces
• On large light graphs in families of polyhedral graphs

Cites work

• 3-paths in graphs with bounded average degree
• A structural property of convex 3-polytopes
• Describing 3-paths in normal plane maps
• Describing short paths in plane graphs of girth at least 5
• Describing tight descriptions of 3-paths in triangle-free normal plane maps
• Light subgraphs of graphs embedded in the plane. A survey
• On the total coloring of planar graphs.
• Optimal unavoidable sets of types of 3-paths for planar graphs of given girth
• Strongly light subgraphs in the 1-planar graphs with minimum degree 7
• Tight descriptions of 3-paths in normal plane maps
• Weight of 3-paths in sparse plane graphs

Cited in

(3)

• 3-paths in graphs with bounded average degree
• On light subgraphs in plane graphs of minimum degree five
• Heavy paths, light stars, and big melons

This page was built for publication: Light subgraphs in graphs with average degree at most four

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