×

zbMATH — the first resource for mathematics

Heavy paths, light stars, and big melons. (English) Zbl 1053.05035
A graph \(H\) is defined to be light in a family \(\mathcal H\) of graphs if there exists a finite number \(w(H,\mathcal H)\) such that each \(G\in\mathcal H\) which contains \(H\) as a subgraph, contains also a subgraph \(K\cong H\) such that the sum of the degrees (in \(G\)) of the vertices of \(K\) (that is, the weight of \(K\) in \(G\)) is at most \(w(H,\mathcal H)\). In this paper the authors study the conditions related to the weight of fixed subgraphs of the plane graphs which can enforce the existence of light graphs in some families of plane graphs. For the families of plane graphs \(\mathcal P(w)\) and triangulations \(\mathcal T(w)\) whose edges are of weight (i.e. the sum of the degrees of endvertices) \(\geq w\) they prove among others the following interesting results:
1. The 4-path \(P_4\) is light in \(\mathcal P(w)\) if and only if \(8\leq w\leq 13\).
2. The 3-cycle \(C_3\) is light in \(\mathcal P(w)\) if and only if \(10\leq w\leq 13\).
3. The 3-cycle \(C_3\) is light in \(\mathcal T(w)\) if and only if \(9\leq w\leq 13\).
4. The 4-cycle \(C_4\) is light in \(\mathcal P(w)\) if and only if \(10\leq w\leq 13\).
5. The star \(K_{1,4}\) is light in \(\mathcal P(w)\) if and only if \(9\leq w\leq 13\).
I. Fabrici and the reviewer proved in [Graphs Comb. 13, 245–250 (1997; Zbl 0891.05025)] that the only light graphs in the family of all 3-connected planar graphs are the paths \(P_k\), for every \(k\geq1\).

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
PDF BibTeX Cite
Full Text: DOI
References:
[1] Borodin, O.V., Solution of problems of kotzig and grünbaum concerning the isolation of cycles in planar graphs, Mat. zametki, 46, 9-12, (1989) · Zbl 0694.05027
[2] Borodin, O.V., On the total colorings of planar graphs, J. reine angew. math., 394, 180-185, (1989) · Zbl 0653.05029
[3] Borodin, O.V., Minimal vertex degree sum of a 3-path in plane maps, Discuss. math. graph theory, 17, 279-284, (1997) · Zbl 0906.05017
[4] Borodin, O.V.; Woodall, D., Short cycles of low weight in normal plane maps with minimum degree five, Discuss. math. graph theory, 18, 159-164, (1998) · Zbl 0927.05069
[5] Fabrici, I., On vertex-degree restricted subgraphs in polyhedral graphs, Discrete math., 256, 105-114, (2002) · Zbl 1007.05063
[6] Fabrici, I.; Hexel, E.; Jendrol’, S.; Walther, H., On vertex-degree restricted paths in polyhedral graphs, Discrete math., 212, 61-73, (2000) · Zbl 0946.05047
[7] Fabrici, I.; Jendrol’, S., Subgraphs with restricted degrees of their vertices in planar 3-connected graphs, Graphs combin., 13, 245-250, (1997) · Zbl 0891.05025
[8] Harant, J.; Jendrol’, S.; Tkáč, M., On 3-connected plane graphs without triangular faces, J. combin. theory ser. B, 77, 150-161, (1999) · Zbl 1027.05030
[9] Jendrol’, S.; Madaras, T., On light subgraphs in plane graphs of minimum degree five, Discuss. math. graph theory, 16, 207-217, (1996) · Zbl 0877.05050
[10] Jendrol’, S.; Madaras, T.; Soták, R.; Tuza, Z., On light cycles in plane triangulations, Discrete math., 197/198, 453-467, (1999) · Zbl 0936.05065
[11] S. Jendrol’, H.J. Voss, Light subgraphs of graphs embedded in 2-dimensional manifolds of Euler characteristic ⩽ 0—a survey, in G. Halász et al. (Eds.), Paul Erdös and his Mathematics II. Based on the Conference, Budapest, 1999. Bolyai Soc. Math. Stud. 11 (2002) 375-411. · Zbl 1037.05015
[12] S. Jendrol’, H.J. Voss, Light subgraphs of graphs embedded in plane and in the projective plane—a survey—, preprint, Inst. of Algebra MATH-AL-2-2001, TU Dresden.
[13] Kotzig, A., Contribution to the theory of Eulerian polyhedra, Mat. časopis. SAV (math. slovaca), 5, 111-113, (1955)
[14] Lebesgue, H., Quelques consequences simples de la formule d’Euler, J. math. pures appl., 19, 19-43, (1940) · JFM 66.0736.03
[15] Madaras, T.; Soták, R., The 10-cycle C10 is light in the family of all plane triangulations with minimum degree five, Tatra mountains math. publ., 18, 35-56, (1999) · Zbl 0951.05031
[16] Mohar, B.; Škrekovski, R.; Voss, H.J., Light subgraphs in planar graphs of minimum degree 4 and edge degree 9, J. graph theory, 44, 261-295, (2003) · Zbl 1031.05075
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.