Information Processing Letters 142 (2019) 64–67

Contents lists available at ScienceDirect

Information Processing Letters

www.elsevier.com/locate/ipl

A note on domination 3-edge-critical planar graphs

Michitaka Furuya a,∗ , Naoki Matsumoto b
a
College of Liberal Arts and Sciences, Kitasato University, 1-15-1 Kitasato, Minami-ku, Sagamihara, Kanagawa 252-0373, Japan
b
Department of Computer and Information Science, Seikei University, 3-3-1 Kichijoji-Kitamachi, Musashino-shi, Tokyo 180-8633, Japan

a r t i c l e i n f o a b s t r a c t

Article history: For a graph G, we let γ (G ) denote the domination number of G. A graph G is 3-edge-
Received 28 February 2018 critical if γ (G ) = 3 and γ (G + xy ) ≤ 2 for all x, y ∈ V (G ) with xy ∈
/ E (G ). In this note, we
Received in revised form 18 October 2018 show that the order of a connected 3-edge-critical planar graph is at most 23.
Accepted 22 October 2018
© 2018 Elsevier B.V. All rights reserved.
Available online 25 October 2018
Communicated by Ryuhei Uehara

Keywords:
Domination 3-edge-critical graph
Planar graph
Bicritical graph
Combinatorial problems

1. Introduction critical if and only if the graph is a complete graph. Fur-

thermore, Sumner and Blitch [5] proved that a graph is
All graphs considered in this paper are finite, simple, 2-edge-critical if and only if each component of its com-
and undirected. plement is a star. Thus we are interested in k-edge-critical
Let G be a graph. We let V (G ) and E (G ) denote the graphs for k ≥ 3. Among them, 3-edge-critical graphs have
vertex set and the edge set of G, respectively. For x ∈ V (G ), been especially studied by many researchers (see, for ex-
let N G (x), N G [x] and d G (x) denote the open neighborhood, ample, [3,4,6,7]).
the closed neighborhood and the degree of x, respectively; In this paper, we study 3-edge-critical planar graphs
thus N G (x) = { y ∈ V (G ) : xy ∈ E (G )}, N G [x] = N G (x) ∪ {x} which focused on, for example, in [2]. Ananchuen and
and d G (x) = | N G (x)|. Let (G ) denote the maximum degree Plummer [2] studied the factor-criticality in 3-edge-critical
of G. For X ⊆ V (G ), we let G [ X ] denote the subgraph of graphs. A graph G is bicritical if G − {x, y } has a perfect
G induced by X . We let K n denote the complete graph of matching for all x, y ∈ V (G ). As a corollary of their main
order n. result, they proved that every 3-connected 3-edge-critical
planar graph having even order is bicritical. Here one ques-
 A subset X of V (G ) is a dominating set of G if V (G ) = tion might be naturally posed: How large is the class of
x∈ X N G [x]. The minimum cardinality of a dominating set
of G, denoted by γ (G ), is called the domination number 3-edge-critical planar graphs? In this note, we give an an-
swer for the question showing that the class is very small.
of G. A dominating set of G with the cardinality γ (G ) is
We prove the following theorem.
called a γ -set of G. For an integer k ≥ 1, a graph G is
k-edge-critical if γ (G ) = k and γ (G + xy ) ≤ k − 1 for all
x, y ∈ V (G ) with xy ∈ / E (G ). Note that a graph is 1-edge- Theorem 1.1. For a connected 3-edge-critical planar graph G,
| V (G )| ≤ 23.

2. Proof of Theorem 1.1

*
Corresponding author.
E-mail addresses: [email protected] (M. Furuya),
[email protected] (N. Matsumoto). In our proof, we will use the following lemmas.

https://doi.org/10.1016/j.ipl.2018.10.014
0020-0190/© 2018 Elsevier B.V. All rights reserved.
 M. Furuya, N. Matsumoto / Information Processing Letters 142 (2019) 64–67 65


(i − 6)ni ≥ (n+
7 − | U | − 1)
i ≥7

+ (d G (u ) − 6) + (d G ( y ) − 6)
u ∈U

≥ (n+
7 − | U | − 1)
Fig. 1. Graph in Lemma 2.2 (where the symbol “+” denotes the join of

vertices).
+ d G (u ) − 6|U | + (n − 9 − 6)
u ∈U

+
Lemma 2.1 (Sumner and Blitch [5]). Let G be a connected = n7 + d G (u ) + n − 7|U | − 16,
3-edge-critical graph. Then |{x ∈ V (G ) : d G (x) ≤ i }| ≤ 3i for u ∈U
each i ≥ 1.
as desired. Thus we may assume that min{d G (x), d G ( y )} ≥
Lemma 2.2 (Ananchuen and Plummer [1]). Let G be a con- 7. Then
nected 3-edge-critical graph. If G has at least two vertices of  
degree exactly 1, then G is the graph depicted in Fig. 1 for n ≥ 1. (i − 6)ni ≥ (n+
7 − | U | − 2) + (d G (u ) − 6)
i ≥7 u ∈U

Proof of Theorem 1.1. Let G be a connected 3-edge-critical + (d G (x) − 6) + (d G ( y ) − 6)

planar graph of order n. By way of contradiction, suppose
that n ≥ 24. ≥ (n+
7 − | U | − 2)

For each i ≥ 1,  let V i = {x ∈ V (G ): d G (x) = i }, and
+ d G (u ) − 6|U | + (n − 3) − 12
set ni = | V i |, n−
i =
+
j ≤i n j and ni =
−
j ≥i n j . Let S =
 u ∈U
1≤ i ≤ 6 V i and S + = V (G ) − S − . Note that | S − | = n−
6.

+
= n7 + d G (u ) + n − 7|U | − 17,
− u ∈U
Claim 2.1. Let h (2 ≤ h ≤ 5) and t ≥ 0. If nh ≤ t, then
   as desired. 2
11 ≤ min{t , 3i } + 3i − (i − 6)ni .
2≤i ≤h h +1 ≤ i ≤ 5 i ≥7
Claim 2.3. Let x, x ∈ V (G ) with xx ∈ / E (G ), and let D be a
γ -set of G + xx . Then | D | = 2 and D contains exactly one of
Proof. Since G contains no K 5 , if n1 ≥ 2, then by x and x . Furthermore, if x ∈ D, then x y ∈/ E (G ) and d G (x) +
Lemma 2.2, n ≤ 7, which is a contradiction. Thus we have d G ( y ) ≥ n − 3 where y is the unique vertex in D − {x}.
n−
1 = n1 ≤ 1. Hence by Lemma 2.1,
⎛ ⎞ Proof. By the definition of the 3-edge-criticality, it suf-
    fices to only show that d G (x) + d G ( y ) ≥ n − 3. Since D =
(6 − i )ni = ⎝ n j⎠ = ni−
{x, y } is a dominating set of G + xx , V (G ) = N G +xx [x] ∪
1≤ i ≤5 1≤ i ≤5 1≤ j ≤ i 1≤ i ≤5
  N G +xx [ y ], and so n ≤ | N G +xx [x]| + | N G +xx [ y ]| = (d G (x) +
≤1+ min{t , 3i } + 3i . 2) + (d G ( y ) + 1). 2
2≤i ≤h h +1 ≤ i ≤ 5
If n−
6 ≤ 4, then by applying Claim 2.1 for h = 5 and
This together with Euler’s formula leads to
t = 4, we have
 
12 ≤ (6 − i )ni ≤ 1 + min{t , 3i } 
i ≥1 2≤i ≤h
11 ≤ (4 + 4 + 4 + 4) − (i − 6)ni ≤ 16 − n+
7,
  i ≥7
+ 3i − (i − 6)ni ,
h +1 ≤ i ≤ 5 i ≥7 and hence n = n− +
6 + n7 ≤ 4 + 5 = 9, which is a contradic-
−
tion. Thus n6 ≥ 5. Since G [ S − ] contains no K 5 , there exist
as desired. 2
two vertices x1 , x1 ∈ S − with x1 x1 ∈ / E (G ). We choose x1
and x1 so that max{d G (x1 ), d G (x1 )} is as small as possible.
Claim 2.2. Let U be a subset of S + , and suppose that there exist Let D 1 be a γ -set of G + x1 x1 . Without loss of general-
x, y ∈ V (G ) − U such that d G (x) + d G ( y ) ≥ n − 3. Then ity, we may assume that x1 ∈ D 1 . By Claim 2.3, we can
⎧ +  write D 1 = {x1 , y 1 } with y 1 = x1 , and we have x1 y 1 ∈
/ E (G )
⎪
⎪n7 + u ∈U d G (u ) + n − 7|U | − 16
⎪ and d G ( y 1 ) ≥ n − d G (x1 ) − 3 ≥ n − 9 (≥ 7). In particular,
 ⎨ (min{d (x), d ( y )} ≤ 6)
G G y1 ∈ S + .
(i − 6)ni ≥ 
⎪n+
⎪ + d ( u ) + n − 7|U | − 17
i ≥7 ⎪
⎩ 7
u ∈ U G
(min{d G (x), d G ( y )} ≥ 7). Claim 2.4.

Proof. If min{d G (x), d G ( y )} ≤ 6, say d G (x) ≤ 6, then (i) n−

4 ≥ 5.
d G ( y ) ≥ n − d G (x) − 3 ≥ n − 9 (≥ 7), and hence (ii) n−
6 ≥ 11.
66 M. Furuya, N. Matsumoto / Information Processing Letters 142 (2019) 64–67

Proof. Since d G ( y 1 ) ≥ 7 and G [ N G ( y 1 )] contains no K 5 , max{d G (x3 ), d G (x3 )} is as small as possible. Let D 3 be
there exist two vertices x, x ∈ N G ( y 1 ) with xx ∈ / E ( G ). a γ -set of G + x3 x3 . We may assume that x3 ∈ D 3 . By
Let D be a γ -set of G + xx . Without loss of general- Claim 2.3, we can write D 3 = {x3 , y 3 } with y 3 = x3 ,
ity, we may assume that x ∈ D. By Claim 2.3, we can and we have x3 y 3 ∈ / E (G ) and d G (x3 ) + d G ( y 3 ) ≥ n − 3.
write D = {x, y } with y = x , and we have x y ∈ / E (G ) and Since x3 y 1 , x3 y 2 ∈ E (G ), y 3 ∈
/ { y 1 , y 2 }. By Claim 2.2 for
d G (x) + d G ( y ) ≥ n − 3. Since x y 1 ∈ E (G ), we have y = y 1 . U = { y 1 , y 2 }, we have
Consequently 
(i − 6)ni
there exist x, y ∈ V (G ) − { y 1 } i ≥7

such that d G (x) + d G ( y ) ≥ n − 3. (2.1) ≥ n+

7 + d G ( y 1 ) + d G ( y 2 ) + n − 7|{ y 1 , y 2 }| − α

Recall that d G ( y 1 ) ≥ n − 9. By (2.1) and Claim 2.2 for U = ≥ n+

7 + (n − 7) + (n − 9) + n − 14 − α
{ y 1 }, we have = n+
7 + 3n − 30 − α , (2.3)

(i − 6)ni ≥ n+
7 + d G ( y 1 ) + n − 7|{ y 1 }| − 17 where
i ≥7

16 (min{d G (x3 ), d G ( y 3 )} ≤ 6)
≥ n+ α=
7 + 2n − 33. (2.2)
17 (min{d G (x3 ), d G ( y 3 )} ≥ 7).

(i) Suppose that n−4 ≤ 4. Then by applying Claim 2.1 for

Applying Claim 2.1 for h = 5 and t = ∞, it follows from
h = 4 and t = 4 and (2.2), we have (2.3) that
 
11 ≤ (4 + 4 + 4 + 15) − (i − 6)ni 11 ≤ (6 + 9 + 12 + 15) − (i − 6)ni
i ≥7 i ≥7

≤ 27 − (n+
7 + 2n − 33),
≤ 42 − (n+
7 + 3n − 30 − α ),

and hence n+ and hence n+ 7 ≤ 61 + α − 3n. This together with Lemma 2.1
7 ≤ 49 − 2n. This together with Lemma 2.1
for i = 6 leads to n = n− + for i = 6 leads to n = n− +
6 + n7 ≤ 18 + (61 + α − 3n). Since
6 + n7 ≤ 18 + (49 − 2n), and so
n ≤ 22, which is a contradiction. n ≥ 24 and α ∈ {16, 17}, this forces n = 24, n− 6 = 18 and
(ii) Suppose that n− 6 ≤ 10. Then by applying Claim 2.1 for
α = 17. In particular min{dG (x3 ), dG ( y 3 )} ≥ 7.
h = 5 and t = 10 and (2.2), we have Since d G ( y 1 ) ≥ n − 7 and d G ( y 2 ) ≥ n − 9, we have | S − −
 N G ( y 1 )| ≤ 6 and | S − − N G ( y 2 )| ≤ 8. Since y 1 , y 2 ∈
/ S − , it
11 ≤ (6 + 9 + 10 + 10) − (i − 6)ni follows that
i ≥7
|N G ( y1 ) ∩ N G ( y2 ) ∩ S −|
≤ 35 − (n+
7 + 2n − 33),
≥ n− − −
6 − | S − N G ( y 1 )| − | S − N G ( y 2 )|
and hence n+ − +
7 ≤ 57 − 2n. This leads to n = n6 + n7 ≤
10 + (57 − 2n), and so n ≤ 22, which is a contradic- ≥ 18 − 6 − 8 = 4.
tion. 2 Let Z = N G ( y 1 ) ∩ N G ( y 2 ) ∩ S − . Since y 1 is adjacent
 to every vertex in Z and G [ Z ∪ { y 1 }] contains no K 5 ,
By Claim 2.4(i) and the fact that G [ 1≤i ≤4 V i ] con- there exist two vertices x4 , x4 ∈ Z with x4 x4 ∈/ E (G ). Then
 
 no K 5 , the choice of x1 and x1 implies that x1 , x1 ∈
tains max{d G (x4 ), d G (x4 )} ≤ 6. On the other hand, max{d G (x3 ),
V
1≤ i ≤ 4 i . In particular, d (
G 1x ) ≤ 4, and so d G ( y 1 ) ≥ n − d G (x3 )} ≥ d G (x3 ) ≥ 7 because min{d G (x3 ), d G ( y 3 )} ≥ 7,
d G (x1 ) − 3 ≥ n − 7. which contradicts the minimality of max{d G (x3 ), d G (x3 )}.
Let X = N G [ y 1 ] ∩ S − . Since d G (x1 ) ≤ 4, we have This completes the proof of Theorem 1.1.
| N G +x1 x [x1 ]| ≤ 6. Since D 1 is a dominating set of G + x1 x1
1
and n− − −
6 ≥ 11, | X | ≥ | S | − 6 = n6 − 6 ≥ 5. Since G [ X ] 3. Concluding remark
contains no K 5 , there exist two vertices x2 , x2 ∈ X with
x2 x2 ∈/ E (G ). Note that y 1 ∈ / {x2 , x2 }. Let D 2 be a γ -set In this note, we proved that if G is a connected 3-edge-
of G + x2 x2 . Without loss of generality, we may assume critical planar graph, then | V (G )| ≤ 23. Since our aim is to
that x2 ∈ D 2 . By Claim 2.3, we can write D 2 = {x2 , y 2 } show that the class of 3-edge-critical planar graphs is very
with y 2 = x2 , and we have x2 y 2 ∈ / E (G ) and d G ( y 2 ) ≥ small, we have not referred to the sharpness of the bound.
n − d G (x2 ) − 3 ≥ n − 9 (≥ 7). In particular, y 2 ∈ S + . Since Indeed, we expect that the bound can be improved. How-
x2 y 1 ∈ E (G ), y 2 = y 1 . ever, it seems a time-consuming work as long as we use
Let Y = N G ( y 1 ) ∩ N G ( y 2 ). Since similar argument in this note even if we slightly improve
the bound. Thus we leave the problem to give a sharp
|Y | = | N G ( y 1 )| + | N G ( y 2 )| − | N G ( y 1 ) ∪ N G ( y 2 )| bound or to characterize the class of 3-edge-critical pla-
nar graphs for the readers.
≥ (n − 7) + (n − 9) − n = n − 16 ≥ 5
One might be interested in a more general class, that is,
and G [Y ] contains no K 5 , there exist two vertices x3 , x3 ∈ Y the class of 3-edge-critical graphs on a closed surface F 2 .
with x3 x3 ∈/ E (G ). We choose x3 and x3 so that We conclude this paper by showing the following theorem.
 M. Furuya, N. Matsumoto / Information Processing Letters 142 (2019) 64–67 67

Theorem 3.1. Let F 2 be a closed surface. Then there exists a con- and hence (G ) ≤ 51 − 6 ( F 2 ), as desired. 2
stant c = c ( F 2 ) such that every connected 3-edge-critical graph
G on F 2 satisfies | V (G )| ≤ c. Acknowledgements

Proof. We show that for every connected 3-edge-critical The authors are grateful to the referees for helpful com-
graph G on F 2 , | V (G )| ≤ (51 − 6 ( F 2 ))3 where  ( F 2 ) is the ments. In particular, the upper bound “26” in previous ver-
Euler characteristic of F 2 . It is known that the diameter of sion was improved to “23”. This work was supported by
a connected 3-edge-critical graph is at most 3 (see [5]). JSPS KAKENHI Grant number 18K13449 (to M.F).
Since | V (G )| ≤ ((G ))d where d is the diameter of G, it
suffices to show that (G ) ≤ 51 − 6 ( F 2 ). References
For each i, we similarly define V i , ni and n− i as in the
[1] N. Ananchuen, M.D. Plummer, Some results related to the toughness
proof of Theorem 1.1. Then by Lemma 2.1 for i = 5,
of 3-domination critical graphs, Discrete Math. 272 (2003) 5–15.
⎛ ⎞ [2] N. Ananchuen, M.D. Plummer, Matching properties in domination crit-
   ical graphs, Discrete Math. 277 (2004) 1–13.
(6 − i )ni = ⎝ n j⎠ [3] Y. Chen, F. Tian, Y. Zhang, Hamilton-connectivity of 3-domination crit-
1≤ i ≤5 1≤ i ≤5 1≤ j ≤ i ical graphs with α = δ + 2, Eur. J. Comb. 23 (2002) 777–784.
 [4] Y. Chen, F. Tian, B. Wei, Codiameters of 3-connected 3-domination
−
= ni ≤ 3 + 6 + 9 + 12 + 15 = 45. critical graphs, J. Graph Theory 39 (2002) 76–85.
[5] D.P. Sumner, P. Blitch, Domination critical graphs, J. Comb. Theory, Ser.
1≤ i ≤5
B 34 (1983) 65–76.
This together with Euler’s formula leads to [6] T. Wang, Q. Yu, A conjecture on k-factor-critical and 3–γ -critical
graphs, Sci. China Math. 53 (2010) 1385–1391.
  [7] E. Wojcicka, Hamiltonian properties of domination-critical graphs,
6 ( F 2 ) ≤ (6 − i )ni ≤ 45 − (i − 6)ni J. Graph Theory 14 (1990) 205–215.
i ≥1 i ≥7
≤ 45 − ((G ) − 6),