ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 355-366
More on the structure of plane graphs with prescribed degrees of vertices, faces, edges and dual edges
Peter Hudak
NESS Kosice Development Center, Moldavská cesta 10/B, 04011 Kosice, Slovakia
Mária Maceková *, Tomás Madaras, Pavol Siroczki
Institute of Mathematics, P.J. Safarik University, Jesenna 5, 04154 Kosice, Slovakia
Received 25 April 2016, accepted 22 August 2016, published online 22 March 2017
We study the families of plane graphs determined by lower bounds 6, p, w, w* on their vertex degrees, face sizes, edge weights and dual edge weights, respectively. Continuing the previous research of such families comprised of polyhedral graphs, we determine the quadruples (2, p, w, w*) for which the associated family is non-empty. In addition, we determine all quadruples which yield extremal families (in the sense that the increase of any value of a quadruple results in an empty family).
Keywords: Plane graph, girth, edge weight, dual edge weight. Math. Subj. Class.: 05C10
1 Introduction
Throughout this paper, we consider connected graphs without loops or multiple edges. Given a graph G = (V, E), the degree d(v) of a vertex v e V is the number of edges incident with v. By k+ or k- we denote any integer not smaller or not greater than k, respectively. Hence, a k-vertex (k+-vertex, k--vertex) is a vertex v with d(v) = k (d(v) > k, d(v) < k, respectively). An edge uv is an (i, j)-edge, if d(u) = i and d(v) = j. For an edge e = uv e E, the weight w(e) of e is the sum d(u) + d(v). The minimum vertex degree of G is the number 6(G) = min{d(v) : v e V}, and the minimum edge weight of G is w(G) = min{w(e) : e e E}. The girth g(G) of G is the length of a shortest cycle of G
* corresponding author
E-mail address: hudakpeterr@gmail.com (Peter Hudak), maria.macekova@student.upjs.sk (Maria Macekova), tomas.madaras@upjs.sk (Tomas Madaras), siroczki@gmail.com (Pavol ¡Siroczki)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
Abstract
356
Ars Math. Contemp. 13 (2017) 275-291
and the double girth of G is defined as the minimum sum of lengths of two distinct cycles of G which share a common edge; it will be denoted as dg(G) (note that g(G) = to if G is a tree, and dg(G) = to if no two cycles of G share an edge). A graph is called planar if it can be drawn in the plane in such a way that, in this drawing, no two edges cross (such a drawing is called a plane graph and it is determined by the triple (V, E, F), where F is the set of faces). The face size d(a) of a face a e F is the number of edges incident with a (incident cut-edges being counted twice). A k-face (k+-face, k--face) is a face a with d(a) = k (d(a) > k, d(a) < k, respectively). The minimum face size of G, denoted p(G), is defined as min{d(a) : a e F} and the minimum dual edge weight of G is the number w*(G) = min{d(a) + d(3) : a, 3 e F, a = ¡3, a, 3 have a common edge}. Note that g(G) < p(G) and dg(G) < w*(g).
For a general graph G, there are no special dependencies of the above mentioned graph invariants apart from the trivial ones: w(G) > 25(G) and dg(G) > 2g(G). On the other hand, these invariants are strongly dependent when additional graph constraints are considered. Particularly, if Gis aplanegraph, then min{5(G), p(G)} < 5; additionally 5(G) > 4 implies p(G) = 3 and p(G) > 4 implies 5(G) < 3. These facts follow easily from Eu-ler's formula for the numbers of vertices, edges and faces of a plane graph. A more subtle analysis of consequences of Euler's formula yields further dependencies: if 5(G) > 3 then w(G) < 13, whereas 5(G) > 4 gives w(G) < 11, see [1]. By considering dual versions of these results, we obtain a dependence between the minimum face size p(G) and the minimum dual edge weight w*(G): if p(G) > 3 then w* (G) < 13 and, for p(G) > 4, w*(G) < 11. Furthermore, the results of the classical paper [9] give that if 5(G) > 3 and p(G) > 4, then w(G) < 8, and 5(G) > 3 together with p(G) = 5 yield w(G) = 6. The mutual dependence of all four values 5(G), p(G), w(G) and w* (G) for polyhedral (that is, 3-connected plane) graphs was studied in [4] giving the characterization of all quadruples (5, p, w, w*) for which the corresponding families of polyhedral graphs of minimum vertex degree at least 5, minimum face size at least p, minimum edge weight at least w and minimum dual edge weight at least w* are non-empty.
The aim of this paper is to extend the results of [4] for wider families of plane graphs with 5 = 2. The graph K2,r shows that w(G) is unbounded for p(G) = 4. On the other hand, recent results by Jendrol' and Macekova [7] and results from [2] show that if g(G) e {5, 6} then w(G) < 7 and, further, if g(G) e {7,8,9,10}, then w(G) < 5 as well as g(G) > 11 implies w(G) = 4. Denoting the set of all plane graphs of minimum degree at least 5, girth at least p, minimum edge weight at least w and minimum double girth at least w* as G(5, p, w, w* ), the equivalent formulation of these results is that the families G(2,5, 8,10), G(2,7, 6,14) and G(2,11, 5, 22) are empty.
In this paper, we prove the following additional results:
Theorem 1.1. The family G(2,3, 7,15) is empty.
Theorem 1.2. The family G(2,3, 9,11) is empty.
Theorem 1.3. The family G(2,3,13,9) is empty.
Theorem 1.4. The families G (2,5,5,27) and G(2, 7, 5,23) are empty.
Theorem 1.5. The family G(2,5, 6,17) is empty.
Theorem 1.6. The family G(2,5, 7,13) is empty.
P. Huddk et al.: More on the structure of plane graphs .
357
For the non-empty families arising from admissible quadruples, we are interested in determining the extremal ones, that is, the families G(J, p, w, w*) such that the increase of any of the values J, p, w and w* results in an empty family. We prove:
Theorem 1.7. The families G(2,4, 8,14), G(2,4,12,10), G(2,6, 5, 26), G(2,6, 6,16), G(2,6, 7,12), G(2,10, 5, 22) are non-empty and extremal.
2 The proofs
For the needs of the proofs we will use the following consequence of Euler's formula with specified parameters a and b (without giving a proof):
Lemma 2.1. Let G be a connected plane graph, a be a positive and b be a non-negative integer. Then
^ (a • d(v) - 2(a + b))+ ^ (b • d(a) - 2(a + b)) = -4(a + b).
c£V (G)	a£F(G)
The common approach used in the majority of proofs in this paper is the discharging method. Assuming the existence of a hypothetical plane counterexample G = (V, E, F) for a particular statement of Theorems 1.1 - 1.7, we define the initial charges of vertices and faces by the function w : V U F ^ Z assigning w(v) = a • d(v) - 2(a + b) for each v G V, and w(a) = b • d(a) — 2(a + b) for each a G F .By Lemma 2.1, J2 xgvuF w(x) = —4(a + b) < 0. Next, we redistribute the initial charges of vertices and faces of G using certain rules which specify, in particular situations, the amount of charge transferred from one element to another; all transfers preserve the total sum of the initial charges. Finally, by case analysis, we show that the final charge y : V U F ^ Q is a non-negative function; this is, however, a contradiction since 0 > J2xeVuF w(x) = J2xeVuF > 0.
We note that, while checking the non-negativity of y, we will usually mention just a minimal set of discharging rules that give y (x) > 0 for an x G V U F, although there may be additional transfers of a positive charge to x.
2.1 Proof of Theorem 1.1
Let the family G(2, 3, 7,15) be non-empty and let G = (V, E, F) be its representative.
Without loss of generality, we can assume that 5+-vertices are not adjacent in G (otherwise we subdivide each (5+, 5+)-edge with anew 2-vertex which yields anew graph G' being again from G(2,3, 7,15)). Therefore each k-face a of G, for k odd, is incident with at most 2-vertices (note that k-face a, for k even, is incident with at most | 2-vertices).
The discharging procedure is based on Lemma 2.1 with a = 1 and b = 0 and the following discharging rules:
R1 Each k-face a, k < 7, distributes its initial charge uniformly to all incident 3+-vertices.
R2 Each k-face a, k > 8, distributes its initial charge uniformly to all incident 4+-vertices.
It follows from the discharging rules that y(a) = 0 for all a G F.
In Table 1 we give the lower bounds for charges received by vertices of graph G from k-faces of G (k > 3):
358
Ars Math. Contemp. 13 (2017) 275-291
k	3	4	5	6	7	8	9	10	11	12+
= 3	2 3	2 3	1 2	1 2	2 5	-	-	-	-	-
= 4	2 3	2 3	1 2	1 2	2 5	1 2	2 5	2 5	1 3	1 3
d(v) > 5	2 3	-1	1 2	2 3	2 5	1 2	2 5	2 5	1 3	1 3
Table 1: Lower bounds for charges sent to vertices of G from a k-face a.
Now, let v e V be a k-vertex, k > 2. We consider the following cases regarding k:
k = 2: Discharging rules do not involve 2-vertices, therefore y(v) = w(v) = 0.
k = 3: The 3-vertices receive negative charge only from incident 7--faces by R1. Since w* (G) > 15, v is incident with at most one 7--face. If a 3-vertex v is incident with an l-face a, 3 < l < 7, then, using Table 1, y(v) > 1 + ( -1) = 3 .If v is incident with no such face, then y>(v) = w(v) = 1.
k = 4: Each 4-vertex v is incident with at most two 7--faces (as w*(G) > 15). If v is incident with a 4--face, then it is incident with at least two 11+-faces, and hence
¥>(v) > 2 + ( -2) + 2 • ( -3) + ( -2) = 0 due to Table 1. Otherwise, v is incident with four 5+-faces and y(v) > 2 + 4 • ( -2) = 0.
k = 5: Each 5-vertex v is incident with at most two 7--faces (as w*(G) > 15). If v is incident with a 3-face, then it is incident with at least two 12+-faces, and hence, using Table 1, y(v) > 3+( - 2 )+2 • ( -1) + ( -1) + ( -1) = 1. If v is incident with one k-face, 4 < k < 7, and four 8+ -faces then y>(v) > 3-1 + 4 • ( - 2) = 0. If v is incident with two 4-faces, then it is incident with three 11+-faces, and y(v) > 3+2^(-1) + 3^ (-3) = 0. If v is incident with a4-face and a 5-face, then it is incident with two 11+-facesanda 10+ -face, and hence y(v) > 3 + (-1) + (- 2 )+2 • (-1) + (- 2) = 10. If it is incident with a 4-face and a 6-face, then it is incident with two 11+-faces and a 9+-face, and hence y(v) > 3+(-1) + (- 2 ) + 2 • (-1) + (- 2) = 15. If v is incident with a 4-face and a 7-face, then it is incident with two 11+-faces and an 8+-face, and hence y(v) > 3 + (-1) + (-2) + 2 • (-1) + (-2) = 10. Finally, if v is incident with faces a and where 5 < d(a),d(£) < 7,then^(v) > 3 + 2 • (-3 ) + 3 • (-1) = 1.
k > 6: Each k-vertex v, k > 6, is incident with at most [|J 7--faces. To estimate the total reception of the vertex v we argue as follows. If v is incident with a 3-face, then it is incident with a 12+-face and they send together a charge -2 + (-3) = -1 to v (according to Table 1). If v is incident with a 4-face, then it is incident with an 11+-face and they send together a charge -1 + (-1) = -4 to v. If v is incident with a 5-face, then it is incident with a 10+-face and they send together a charge -2 + (-5) = -10 to v. If v is incident with a 6-face, then it is incident with a 9+-face and they send together a charge -2 + (-2) = -H to v. And finally, if v is incident with a 7-face, then it is incident with an 8+-face and they send together a charge -1 + (-1 ) = -10 to v. Thence it follows, that each face sends in average a charge at least -2 to v and therefore y(v) > k - 2 + k • (-2) = f - 2 > 0 for k > 6.
Hence, all elements of G have non-negative final charge, giving the desired contradiction.
P. Huddk et al.: More on the structure of plane graphs .
359
2.2 Proof of Theorem 1.2
Let the family G(2, 3, 9,11) be non-empty and G = (V, E, F) be its representative.
The discharging procedure is based on Lemma 2.1 with a =1 and b = 0 and the following discharging rules:
R1 Each k-face, k < 5, divides its initial charge uniformly among all incident 3+-vertices.
R2 Each k-face, k > 6, sends a charge of size — 3 to each incident 4-vertex.
R3 Each k-face, k > 6, distributes its residual charge (after application of R2) uniformly to all incident 5+-vertices.
It follows from the discharging rules that y>(a) = 0 for all a e F. In Table 2 we give the lower bounds for charges received by vertices of graph G from k-faces of G, k > 3:
k	3	4	5	6	7	8	9+
= 3	2 3	2 3	1 2	-	-	-	-
= 4	2 3	2 3	1 2	1 3	1 3	1 3	1 3
d(v) = 5	2 3	2 3	1 2	1 2	5 12	2 5	1 3
d(v) = 6	2 3	2 3	1 2	2 3	1 2	1 2	2 5
d(v) > 7	-1	-1	2 3	2 3	1 2	1 2	2 5
Table 2: Lower bounds for charges sent to vertices of G from a k-face a.
Now, let v e V be a k-vertex, k > 2. We consider the following cases regarding k: k = 2: Discharging rules do not involve 2-vertices, therefore y(v) = w(v) = 0.
k = 3: Each 3-vertex v is incident with at most one 5--face (as w*(G) > 11). Hence, using Table 2, y>(v) > 1 + ( — |) = 1.
k = 4: Each 4-vertex v is incident with at most two 5--faces (as w*(G) > 11). Hence, according to Table 2, ^(v) > 2 + 2 • ( — -) + 2 • ( — 1) = 0.
k = 5: Each 5-vertex v is incident with at most two 5--faces (as w*(G) > 11). Hence,
^(v) > 3 + 2 • ( — §) + 3 • ( — 1 ) = 1.
k = 6: Each 6-vertex v receives from each face charge at least —§ and therefore, <^(v) > 4 + 6 • ( — §) = 0.
k = 7: If v is incident with three 3- or 4-faces, then it is incident with four 8+-faces and, using Table 2, y>(v) > 5 + 3 • ( — 1) + 4 • ( — §) =0. If v is incident with two 3- or 4-faces, then it is incident with at least three 8+-faces and <^(v) > 5 + 2 • ( — 1) + 3 • ( — 1) + 2 • ( — § ) = 6 .If v is incident with one 3- or 4-face, then it is incident with at least two 8+-faces and <^(v) > 5 + ( —1) + 2 • ( — §) + 4 • ( — §) = 1. Otherwise,
it is incident only with 5+-faces and y(v) > 5 + 7 • ( — -)
2 ) = 1 3 > 3'
360
Ars Math. Contemp. 13 (2017) 275-291
k > 8: Let s be the number of 3- and 4-faces incident with k-vertex v and t be the number of 8+-faces incident with v. As w*(G) > 11, we have t > s and s < [2J- Then
y(v) > k -2 + s • ( -1)+1 • ( -2) + (k - s -t) • ( -1) = k -2- s • 3 +1 • 1-k• 2 > I - s • 1 - 2 > | - - 2 = | - 2 > 0 for k >8.
3	6	— 3 12	4	—	—
Hence, all elements of G have non-negative final charge, a contradiction. 2.3 Proof of Theorem 1.3
Let the family G(2, 3,13, 9) be non-empty and G = (V, E, F) be its representative.
The discharging procedure is based on Lemma 2.1 with a =1 and b = 0 and the following discharging rules:
R1 a) Each face a sends a charge of size - 3 to each incident 3-vertex. b) Each face a sends a charge of size - 2 to each incident 4-vertex.
R2 Each face a distributes its residual charge (after the application of R1a and R1b) uniformly among all incident 5+-vertices.
It follows from the discharging rules that y(a) = 0 for all a G F (the faces are able to distribute the charge, since there are always 5+-vertices in the graph).
In Table 3 we give the lower bounds for charges received by vertices of graph G from k-faces of G (k > 3) after the application of the rule R1:
k	3	4	5	6+
5 < d(v) < 8	2 3	2 3	1 2	1 2
d(v) = 9	3 4	2 3	1 2	1 2
d(v) = 10	5 6	2 3	5 9	1 2
d(v) > 11	-1	-1	2 3	2 3
Table 3: Lower bounds for charges sent to vertices of G from a k-face a.
Now, let v g V be a k-vertex, k > 2. We consider the following cases regarding k:
k = 2: Discharging rules do not involve 2-vertices, therefore y(v) = w(v) = 0.
k = 3: Each 3-vertex v receives - 3 from all incident faces, hence y(v) = 1+3-(-3) = 0.
k = 4: Each 4-vertex v receives - 2 from all incident faces, hence y(v) = 2+4-(-2) = 0.
5 < k < 8: Let s and t be the numbers of 4-- and 5+ -faces incident with a k-vertex v, respectively. As w*(G) > 9, we have t > s and s < [|J. Then, using Table 3,
^(v) > k - 2+s • (-2)+1 • (-2) > k - 2+ s I i • (-3)+[ 11 • (-2) > 1 - 2 > 0
for k > 5.
k = 9: As each 9-vertex receives, according to Table 3, a charge of at least - 4 from each incident face, we have that y(v) > 7 + 9 • (-4) = 4 > 0.
k = 10: Each 10-vertex is incident with at least five 5+-faces (as w*(G) > 9). Therefore
^(v) > 8 + 5 • (-§) + 5 • (-§) = H > 0.
P. Huddk et al.: More on the structure of plane graphs .
361
k = 11: Each 11-vertex is incident with at least six 5+-faces (as w*(G) > 9). Therefore
^(v) > 9 + 6 • (-§)+5 • (-1)=0.
k > 12: Let s and t be the numbers of 4-- and 5+-faces incident with a k-vertex v, respectively. As w*(G) > 9, we have t > s and s < |_|J. Then <^(v) > k - 2 + s • (-1) + t • (-§) > k - 2 + [ | J • (-1) + [ 11 • (-§) > | - 2 > 0 for
k > 12.
Hence, all elements of G have non-negative final charge, a contradiction.
2.4	Proof of Theorem 1.4
Let the families G(2,5,5, 27) and G(2,7, 5, 23) be non-empty and G| and G| be their
respective representatives. Each face a of G^ and G2 is incident with at most ^^ 2-
vertices (as w(G*) > 5 for i e {1, 2}). Then, after suppressing all 2-vertices of G| and G§, respectively, we obtain graphs Gi, G2 with ¿(Gj) > 3, i e {1,2}. Moreover, G1 belongs to the family G(3, 3, 6,14) and G2 is from G(3,4, 6,12), which contradicts the fact that these families were proven to be empty (see [4]).
2.5	Proof of Theorem 1.5
Let G = (V, E, F) e G(2,5, 6,17) be a counterexample to the theorem. Without loss of generality, we assume that 4+-vertices are not adjacent in G (otherwise we subdivide each (4+, 4+)-edge in G with a new 2-vertex, which yields a new counterexample G' e G(2,5, 6,17)). Therefore, each k-face a of G, for k odd, is incident with at most 2-vertices (note that k-face a, for k even, is incident with at most | 2-vertices).
The discharging procedure is based on Lemma 2.1 with a = 2, b =1 and the following discharging rules:
R1 Each vertex v distributes its initial charge uniformly to all incident faces.
R2 Each 11+-face a sends a charge of size 1 to each adjacent face (through every common edge).
By R1, y(v) = 0 for all v e V. Since w(G) > 6, every 2-vertex of G is adjacent only to 4+-vertices and every its 3-vertex is adjacent only to 3+-vertices.
Let a e F be a k-face, k > 5. We consider the following cases regarding k:
k = 5: All faces adjacent to a are 12+-faces (as w*(G) > 17) and a is incident with at most one 2-vertex. If a is incident with exactly one 2-vertex, then it is incident with at least two 4+-vertices and hence y(a) > -1 + (-1) + 2 • § + 5 • 4 = 1. Finally, if a is not incident with any 2-vertex, then y>(a) >-1 + 5 • 4 = 1.
k = 6: All faces adjacent to a are 11+-faces (as w*(G) > 17). If a is incident with three 2-vertices, then it is incident with three 4+-vertices. Hence y(a) > 0 + 3 • (-1) + 3 • i + 6 • 4 = 0. If a is incident with two 2-vertices, then it is incident with at least three 4+-vertices, giving y>(a) > 0 + 2 • (-1) + 3 • § + 6 • 4 = 1. If a is incident with at most one 2-vertex, then y>(a) > 0 + (-1) + 6 • 4 = 1.
k = 7: a is incident with at most two 2-vertices. If a is incident with two 2-vertices, then it is incident with at least three 4+-vertices. Hence y(a) > 1 + 2 • (-1) + 3 • § = 1 by R1. Otherwise, if a is incident with at most one 2-vertex, then y>(a) > 1 + (-1) =0.
362
Ars Math. Contemp. 13 (2017) 275-291
k = 8: If a is incident with four 2-vertices, then it is incident with four 4+-vertices. Hence y>(a) > 2 + 4 • ( — 1) + 4 • 2 = 0 by R1. If a is incident with three 2-vertices, then it is incident with at least four 4+-vertices, giving y>(a) > 2 + 3 • ( —1) + 4 • 2 = 1. Finally, if a is incident with at most two 2-vertices, then y>(a) > 2 + 2 • ( — 1) = 0.
k = 9: a is incident with at most three 2-vertices, thus we have that <^(a) > 3 + 3 • ( —1) = 0.
k = 10: If a is incident with five 2-vertices, then it is incident with five 4+-vertices. Hence ¥>(a) > 4 + 5 • ( —1) + 5 • 1 = 2 byR1. Otherwise, if a is incident with at most four 2-vertices, then <^(a) > 4 + 4 • ( — 1) = 0.
k =11: a is incident with at most four 2-vertices. If a is incident with four 2-vertices, then it is incident with at least five 4+-vertices. Hence y(a) > 5+4-( —1) + 5- 2 — 11 4 = 4 by R1 and R2. If a is incident with three 2-vertices, then it is incident with at least four 4+-vertices, giving y>(a) > 5 + 3 • ( — 1) +4 • 1 — 11 • 4 = 5. Finally, if a is incident with at most two 2-vertices, then <^(a) > 5 + 2 • ( — 1) — 11 • 1 = 1.
k > 12: Let s and t be numbers of 2— and 4+—vertices incident with a, respectively. As
w(G) > 6, we have t > s and s < [|j. Then <^(a) > k — 6 + s • ( —1)+1 • 2 — 1 • k > 3 • k — 6 — 2 • s > 4 • k — 6 — 1 • [|j > 0 for k > 12.
Hence, all elements of G have non-negative final charge, a contradiction. 2.6 Proof of Theorem 1.6
Let the family G(2,5,7,13) be non-empty and G = (V, E, F) be its representative. Without loss of generality, we can assume that 5+-vertices are not adjacent in G (otherwise we subdivide each (5+, 5+)-edge in G with a new 2-vertex, which yields a new counterexample G' G G(2,5, 7,13)). Therefore, each k-face a of G, for k odd, is incident with at most 2-vertices (note that k-face a, for k even, is incident with at most 2 2-vertices).
The discharging procedure is based on Lemma 2.1 with a = 2, b = 1 and the following discharging rules:
R1 Each vertex v divides its initial charge uniformly among all incident faces.
R2 Each 7+-face a sends a charge of size 25 to each adjacent face (through every common edge).
By R1, y(v) = 0 for all v G V. Since w(G) > 7, every 2-vertex of G is adjacent only to 5+-vertices and every its 3-vertex is adjacent only to 4+-vertices.
Let a G F be a k-face, k > 5. We consider the following cases regarding k:
k = 5: All faces adjacent to a are 8+-faces (as w*(G) > 13). If a is incident with a 2-vertex, then it is incident with at least two 5+ -vertices and hence <^(a) > —1 + ( —1) + 2 • 4 + 5 • 25 = 1. Otherwise, if a is not incident with any 2-vertex, then it is incident with at least three 4+-vertices, and therefore y(a) > —1 + 3-1 +5-25 = 11.
k = 6: All faces adjacent to a are 7+-faces (as w*(G) > 13). If a is incident with three 2-vertices, then it is incident with three 5+-vertices. Hence y(a) > 0 + 3 • ( — 1) + 3 • 5 + 6 • 25 = 25. If a is incident with two 2-vertices, then it is incident with at least three 5+-vertices, giving y(a) > 0 + 2 • ( — 1) +3 • 4 +6 • 25 = H .If a is
P. Huddk et al.: More on the structure of plane graphs .
363
incident with exactly one 2-vertex, then it is incident with at least two 5+ -vertices and thus y(a) > 0 + ( —1) + 2 • 4 + 6 • 2f = if. Finally, if a is not incident with a 2-vertex, then it receives non-negative charge from each incident vertex, therefore
y(a) > w(a) = 0.
k = 7: If a is incident with two 2-vertices, then it is incident with at least three 5+-vertices, so y(a) > 1 + 2 • ( —1) + 3 • 4 + 7 • (-2f) = If.If a is incident with exactly one 2-vertex, then it is incident with at least two 5+ - vertices and hence y (a) > 1 + (— 1) + 2 • f+7 • (— 2f) = 2f. Finally, if a is not incident with a 2-vertex, then it receives nonnegative charge from each incident vertex and, by R2, y(a) > 1 + 7 • ( — 2f) = 2f.
k > 8: Let s and t be numbers of 2— and 5+-vertices incident with a, respectively. As
w(G) > 7, we have t > s and s < [ f J. Then y(a) > k — 6+s-(-1)+t • 4 — 2f •k > 2|k — s — 6 > 2fk — [fJ • 1 — 6 >i9k — 6 > 0 for k > 8.
Hence, all elements of G have non-negative final charge, a contradiction.
2.7 Proof of Theorem 1.7
For each of the mentioned six families, we describe a representative and show that the increase in any of the four parameters results in an empty family.
The family G(2,4,8,14) contains, as a representative, the graph obtained from the dodecahedron by replacing each edge uv by a 4-cycle uxvy with x, y being 2-vertices. Furthermore, G(3,4,8,14) c G(3,4, 7,9) = 0 by [4], G(2, 5, 8,14) c G(2,5,8,10) = 0 by [2] and [7], G(2,4, 9,14) c G(2,3,9,11) = 0 by Theorem 1.2, and G(2,4, 8,15) c G(2,3, 7,15) = 0 by Theorem 1.1.
A representative of G(2,4,12,10) is obtained from the icosahedron by replacing each edge uv by a 4-cycle uxvy with x,y being 2-vertices. Furthermore, G(3,4,12,10) c G(3,4, 7, 9) = 0 by [4], G(2, 5,12,10) c G(2, 5, 8,10) = 0 by [2, 7], G(2, 4,13,10) c G(2,3,13, 9) = 0 by Theorem 1.3, and finally G(2,4,12,11) c G(2, 3, 9,11) = 0 by Theorem 1.2.
For G(2,6,5, 26), a suitable representative can be obtained, for example, by subdividing each edge of the graph of the truncated dodecahedron. Note that G(3, 6, 5, 26) = 0
(if ¿(G) > 3, then p(G) < 5). Furthermore, by Theorem 1.4, G(2,7,5,26) c G(2,7, 5, 23) = 0, G(2,6, 5, 27) c G(2,5,5, 27) = 0 and, by Theorem 1.5, G(2, 6, 6, 26) c G(2, 5, 6,17) = 0.
By subdividing each edge of the graph of icosidodecahedron, we obtain a representative of G(2,6, 6,16). Again, G(3, 6, 6,16) = 0 (if ¿(G) > 3, then p(G) < 5) and G(2,7, 6,16) c G(2,7,6,14) = 0 by [2, 7], G(2, 6, 7,16) c G(2, 5, 7,13) = 0 by Theorem 1.6, G(2, 6,6,17) c G(2, 5,6,17) = 0 by Theorem 1.5.
A representative of G(2, 6,7,12) is obtained by subdividing each edge of the icosahedron graph. Further, G(3,6, 7,12) = 0 (if ¿(G) > 3, then p(G) < 5), G(2, 7,7,12) = 0 (if p(G) > 7, then w*(G) > 2p(G) = 14), G(2, 6,8,12) c G(2,5, 8,10) = 0 by [2, 7], and G(2,6, 7,13) c G(2,5,7,13) = 0 by Theorem 1.6.
A representative of G(2,10, 5, 22) is obtained by subdividing each edge of the truncated icosahedron. Further, G(3,10,5, 22) = 0 (if ¿(G) > 3, then p(G) < 5), G(2,11, 5,22) = 0 by [2] and [7], G(2,10, 6,22) c G(2,5,6,17) = 0 by Theorem 1.5, and finally G(2,10,5, 23) c G(2,7,5,23) = 0 by Theorem 1.4.
364
Ars Math. Contemp. 13 (2017) 275-291
3 Concluding remarks
A possible common way how to visualize the dependence of S, p, w, w* for families of plane graphs is to construct a diagram of a partially ordered set depicting the hierarchy of all non-empty families (generated by quadruples (S, p,w,w* )) under the set inclusion partial ordering. For S > 3, a partially ordered set of generated families of polyhedral graphs is shown in Figure 1 (this also corrects the error in the original diagram in [4]):
(3,3,6,6)
Figure 1: The hierarchy of families of polyhedral graphs generated by (5, rho, w, w*).
The results for 5 = 2 are presented in Table 4 indexed by values of girth (rows) and edge weight (columns) such that, the corresponding table entry shows the maximal admissible value of dual edge weight. The value to in the first column is due to the fact that, in the graph obtained from Cn (n arbitrarily large) by replacing every edge with two disjoint paths of length 2, the dual edge weight is unbounded. The value 8 in the last column results from the graph K2,r for large r. The bold values correspond to extremal families.
The verification that we found all extremal classes can be done manually, or, as we did, using a simple computer program. Iterating over all possible classes (2, p, w, w*) check for every non-extremal class that it is either covered by an extremal class (all parameters are less or equal than for some extremal class) or by an empty class (all parameters are greater or equal than for some empty class).
Let us note that all extremal classes must have all parameters less or equal to 26, because every class that has at least one parameter greater than 26 is empty (it is a subset of G(2,3,13, 9), G(2, 5, 5, 27) or G(2,3, 7,15), which are all proven to be empty) or it is a part of one of two infinite chains.
P. Huddk et al.: More on the structure of plane graphs .
365
^^^ w p	4	5	6	7	8	9	10	11	12	13+
3	TO	TO	TO	14	14	10	10	10	10	8
4	TO	TO	œ	14	14	10	10	10	10	8
5	TO	26	16	12						
6	TO	26	16	12						
7	TO	22								
8	TO	22								
9	TO	22								
10	TO	22								
11+	œ									
Table 4: The table of admissible values for quadruples (2, p, w, w*).
The mutual dependence of the invariants J, p, w, w* can also be studied for graphs embedded into higher surfaces. Partial results were obtained for embedded graphs with J(G) = 3 and orientable genus 7(G) in [6], it was proved that w(G) < 27(G) + 13 if 0 < 7(G) < 3 and w(G) < 47(G) + 7 if 7(G) > 3, whereas w(G) < 47(G) + 5 if Y(G) > 1 and g(G) > 4. For graphs with non-orientable genus 7(G), it was proved in [8] that w(G) < 27(g) + 11 if 1 < 7(G) < 2, and w(G) < 27(G) +9 in 3 < 7(G) < 5 with w(G) < 27(G) + 7 for 7(G) > 6; furthermore, if g(G) > 4, then w(G) < 27(G) + 5 for 7(G) > 2 and w(G) < 8 for 7(G) = 1. Note, however, that for embedded graphs with fixed genus, the invariant w* (G) need not be well-defined, as G might have a single face. This could be overcome by considering polyhedral embeddings (whose facial walks are cycles and each two of them have at most a vertex or an edge in common).
There exist many graph families whose members do not involve a fixed genus embedding, but they possess structural properties which are analogous to ones for plane or embedded graphs nonetheless. A particularly interesting family in this direction is the family of 1-planar graphs, that is, the family of graphs which can be drawn in the plane in such a way that each edge is crossed at most once. It is known that if G is a 1-planar graph, then J(G) < 7 and, in addition, w(G) < 40 if G is 3-connected, see [3]. For a 1-planar graph G with J(G) G {5,6, 7} it was proved in [5] that w(G) < 14. A partial dependence between J(G) and g(G) is also known: if J(G) > 5, then g(G) < 4 and g(G) = 3 for J(G) G {6,7}, see [3]; however, for J(G) G {3,4}, an upper bound for g(G) is still not known. Also, not much is known on the dependence of dg(G) (which is a vague analogue of w* (G) for non-embedded graphs) on w(G), g(G) and J (G): so far, the only result is the one from [10] that if J(G) > 6 and w(G) > 13, then dg(G) = 6.
Acknowledgements
This work was supported by the Slovak VEGA Grant No. 1/0368/16, by P. J. Safarik University grant VVGS-2014-179, and by VVGS-PF-2015-484. We thank the referees for their time and comments.
366
Ars Math. Contemp. 13 (2017) 275-291
References
[1]	O. V. Borodin, On the total coloring of planar graphs, J. Reine Angew. Math. 394 (1989), 180-185, doi:10.1515/crll.1989.394.180, http://dx.doi.org/10.1515/ crll.1989.394.180.
[2]	D. W. Cranston and D. B. West, A guide to the discharging method, 2013, arXiv: 1306.4434 [math.CO].
[3]	I. Fabrici and T. Madaras, The structure of 1-planar graphs, Discrete Math. 307 (2007), 854865, doi:10.1016/j.disc.2005.11.056, http://dx.doi.org/10.1016/j.disc.2005. 11.056.
[4]	B. Ferencova and T. Madaras, On the structure of polyhedral graphs with prescribed edge and dual edge weight, Acta Univ. M. Belii Ser. Math. (2005), 13-18.
[5]	D. Hudak and P. Sugerek, Light edges in 1-planar graphs with prescribed minimum degree, Discuss. Math. Graph Theory 32 (2012), 545-556, doi:10.7151/dmgt.1625, http://dx. doi.org/10.7151/dmgt.162 5.
[6]	J. Ivanco, The weight of a graph, Ann. Discrete Math. 51 (1992), 113116, doi:10.1016/S0167-5060(08)70614-9, http://dx.doi.org/10.1016/ S0167-5060(08)70614-9.
[7]	S. Jendrol' and M. Macekova, Describing short paths in plane graphs of girth at least 5, Discrete Math. 338 (2015), 149-158, doi:10.1016/j.disc.2014.09.014, http://dx.doi.org/10. 1016/j.disc.2014.09.014.
[8]	S. Jendrol' and M. Tuharsky, A Kotzig type theorem for non-orientable surfaces, Math. Slovaca 56 (2006), 245-253.
[9]	H. Lebesgue, Quelques consequences simples de la formule d'Euler, J. Math. Pures Appl. 19 (1940), 27-43.
[10] X. Zhang andG. Liu, On the lightness of chordal 4-cycle in 1-planar graphs with high minimum degree, Ars Math. Contemp. 7 (2014), 281-291.