Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 325–331
On the core of a unicyclic graph
Vadim E. Levit
Ariel University Center of Samaria, Israel
Eugen Mandrescu
Holon Institute of Technology, Israel
Received 23 February 2011, accepted 22 December 2011, published online 10 April 2012
Abstract
A set S ⊆ V is independent in a graph G = (V,E) if no two vertices from S are
adjacent. By core(G) we mean the intersection of all maximum independent sets. The
independence number α(G) is the cardinality of a maximum independent set, while µ(G)
is the size of a maximum matching in G.
A connected graph having only one cycle, say C, is a unicyclic graph. In this paper we
prove that if G is a unicyclic graph of order n and n − 1 = α(G) + µ(G), then core (G)
coincides with the union of cores of all trees in G− C.
Keywords: Maximum independent set, core, matching, unicyclic graph, König-Egerváry graph.
Math. Subj. Class.: 05C69, 05C70
1 Introduction
Throughout this paper G = (V,E) is a simple (i.e., a finite, undirected, loopless and
without multiple edges) graph with vertex set V = V (G) and edge set E = E(G). If
X ⊂ V , then G[X] is the subgraph of G spanned by X . By G−W we mean the subgraph
G[V −W ], if W ⊂ V (G). For F ⊂ E(G), by G − F we denote the partial subgraph
of G obtained by deleting the edges of F , and we use G − e, if W = {e}. If A,B ⊂ V
and A ∩ B = ∅, then (A,B) stands for the set {e = ab : a ∈ A, b ∈ B, e ∈ E}. The
neighborhood of a vertex v ∈ V is the set N(v) = {w : w ∈ V and vw ∈ E}, and
N(A) = ∪{N(v) : v ∈ A}, N [A] = A ∪ N(A) for A ⊂ V . By Cn,Kn we mean the
chordless cycle on n ≥ 4 vertices, and respectively the complete graph on n ≥ 1 vertices.
A set S of vertices is independent if no two vertices from S are adjacent, and an in-
dependent set of maximum size will be referred to as a maximum independent set. The
E-mail addresses: levitv@ariel.ac.il (Vadim E. Levit), eugen m@hit.ac.il (Eugen Mandrescu)
Copyright c© 2012 DMFA Slovenije
326 Ars Math. Contemp. 5 (2012) 325–331
independence number of G, denoted by α(G), is the size of a maximum independent set of
G. Let Ω(G) denote the family {S : S is a maximum independent set of G}, while
core(G) = ∩{S : S ∈ Ω(G)} [11].
An edge e ∈ E(G) is α-critical whenever α(G − e) > α(G). Notice that the inequalities
α(G) ≤ α(G− e) ≤ α(G) + 1 hold for each edge e.
A matching (i.e., a set of non-incident edges of G) of maximum cardinality µ(G) is
a maximum matching, and a perfect matching is one covering all vertices of G. An edge
e ∈ E(G) is µ-critical provided µ(G− e) < µ(G).
Theorem 1.1. [13] For every graph G no α-critical edge has an endpoint in N [core(G)].
It is well-known that
bn/2c+ 1 ≤ α(G) + µ(G) ≤ n
hold for every graph G with n vertices. If α(G) + µ(G) = n, then G is called a König-
Egerváry graph [3, 19]. Several properties of König-Egerváry graphs are presented in
[6, 9, 10, 12, 15, 16].
It is known that every bipartite graph is a König-Egerváry graph as well [5, 8]. This
class includes also non-bipartite graphs (see, for instance, the graph G in Figure 1).
w w w w w
w w
@
@
@
a
b
cu v
x
y
G
Figure 1: A König-Egerváry graph with α(G) = |{a, b, c, x}| and µ(G) = |{au, cv, xy}|.
Theorem 1.2. If G is a König-Egerváry graph, then
(i) [12] every maximum matching matches N(core(G)) into core(G);
(ii) [13] H = G−N [core(G)] is a König-Egerváry graph with a perfect matching and
each maximum matching of H can be enlarged to a maximum matching of G.
The graph G is called unicyclic if it is connected and has a unique cycle, which we
denote by C = (V (C), E (C)). Let
N1(C) = {v : v ∈ V (G)− V (C), N(v) ∩ V (C) 6= ∅},
and Tx = (Vx, Ex) be the tree of G− xy containing x, where x ∈ N1(C), y ∈ V (C).
w w w w w w
w w w w
@
@
@
@
@
@
u v x y w c
a b d t
G w w w
w w
@
@
@
u v x
a b
Tx
Figure 2: G is a unicyclic non-König-Egerváry graph with V (C) = {y, d, t, c, w}.
Unicyclic graphs keep enjoying plenty of interest, as one can see, for instance, in [1, 4,
7, 14, 18, 20, 21].
In this paper we analyze the structure of core(G) for a unicyclic graph G.
V. E. Levit and E. Mandrescu: On the core of a unicyclic graph 327
2 Results
If G is a unicyclic graph, then there is an edge e ∈ E (C), such that µ(G − e) = µ(G),
because for each pair of edges, consecutive on C, at most one could be µ-critical. Let us
mention that α(G) ≤ α(G − e) ≤ α(G) + 1 holds for each edge e ∈ E (G). Every edge
of the unique cycle could be α-critical; e.g., the graph G from Figure 2, which has also
additional α-critical edges (e.g., the edge uv).
Notice that the bipartite graph Tx from Figure 2 has only two maximum matchings,
namely, M1 = {ax, uv} and M2 = {bx, uv}, while for each maximum matching there is
a vertex in core(Tx) = {a, b} not saturated by that matching.
Lemma 2.1. For every bipartite graph G, a vertex v ∈ core(G) if and only if there exists
a maximum matching that does not saturate v.
Proof. Since v ∈ core(G), it follows that α(G− v) = α(G)− 1. Consequently, we have
α(G) + µ(G)− 1 = |V (G)| − 1 = |V (G− v)| = α(G− v) + µ(G− v)
which implies that µ(G) = µ(G− v). In other words, there is a maximum matching in G
not saturating v.
Conversely, suppose that there exists a maximum matching in G that does not saturate
v. Since, by Theorem 1.2(i), N(core(G)) is matched into core(G) by every maximum
matching, it follows that v /∈ N(core(G)).
Assume that v /∈ core(G). By Theorem 1.2(ii), every maximum matching M of G is
of the form M = M1 ∪M2, where M1 matches N(core(G)) into core(G), while M2 is a
perfect matching of G−N [core(G)]. Thus v is saturated by every maximum matching of
G, in contradiction with the hypothesis on v.
Remark 2.2. Lemma 2.1 fails for non-bipartite König-Egerváry graphs; e.g., every maxi-
mum matching of the graph G from Figure 1 saturates c ∈ core(G) = {a, b, c}.
Lemma 2.3. If G is a unicyclic graph of order n, then n− 1 ≤ α(G) + µ(G) ≤ n.
Proof. If e = xy ∈ E(C), thenG−e is a tree, becauseG is connected. Hence, α(G−e)+
µ(G − e) = n. Clearly, α(G − e) ≤ α(G) + 1, while µ(G − e) ≤ µ(G). Consequently,
we get that
n = α(G− e) + µ(G− e) ≤ α(G) + µ(G) + 1,
which leads to n− 1 ≤ α(G) + µ(G). The inequality α(G) + µ(G) ≤ n is true for every
graph G.
Remark 2.4. If G has n vertices, p connected components, say Hi, 1 ≤ i ≤ p, and each
component contains only one cycle, then one can easily see that n−p ≤ α(G)+µ(G) ≤ n,
because α(G) =
p∑
i=1
α(Hi) and µ(G) =
p∑
i=1
µ(Hi).
While C2k, k ≥ 2, has no α-critical edge at all, each edge of every odd cycle C2k−1,
k ≥ 2, is α-critical. This property is partially inherited by unicyclic graphs.
Lemma 2.5. Let G be a unicyclic graph of order n. Then n − 1 = α(G) + µ(G) if and
only if each edge of its unique cycle is α-critical.
328 Ars Math. Contemp. 5 (2012) 325–331
Proof. Assume that n− 1 = α(G) + µ(G). Since G is connected, for each e ∈ E(C) the
graph G− e is a tree. Hence, we have
α(G− e)− α(G) + µ(G− e)− µ(G) = 1,
which implies µ(G− e) = µ(G) and α(G− e) = α(G) + 1, since
−1 ≤ µ(G− e)− µ(G) ≤ 0 ≤ α(G− e)− α(G) ≤ 1.
In other words, every e ∈ E(C) is α-critical.
Conversely, let e ∈ E (C) be such that µ(G− e) = µ(G); such an edge exists, because
no two consecutive edges on C could be µ-critical. Since e is α-critical, and G − e is a
tree, we infer that
n− 1 = α(G− e) + µ(G− e)− 1 = α(G) + µ(G),
and this completes the proof.
Combining Lemma 2.5 and Theorem 1.1, we infer the following.
Corollary 2.6. If G is a unicyclic non-König-Egerváry graph, then no vertex of its unique
cycle belongs to N [core(G)].
Remark 2.7. Corollary 2.6 is true also for some unicyclic König-Egerváry graphs; e.g.,
the graph H1 from Figure 3. However, the König-Egerváry graph H2 from the same figure
satisfies N [core(H2)] ∩ V (C) = {u} 6= ∅.
w w w w w
w w w w
a
b
c d
H1 w w w w w
w w w w
@
@
@
x y
zu v
H2
Figure 3: H1 and H2 have N [core(H1)] = {a, b, c}, N [core(H2)] = {x, y, z, u, v}.
Lemma 2.8. Let G be a unicyclic graph of order n. If there exists some x ∈ N1(C), such
that x ∈ core(Tx), then G is a König-Egerváry graph.
Proof. Let x ∈ core(Tx), y ∈ N (x) ∩ V (C), and z ∈ N (y) ∩ V (C). Suppose, to the
contrary, that G is not a König-Egerváry graph. By Lemmas 2.3 and 2.5, the edge yz is
α-critical. Hence y /∈ core(G), which implies that α(G) = α(G− y). In accordance with
Lemma 2.1, there exists a maximum matching Mx of Tx not saturating x. Combining Mx
with a maximum matching ofG−y−Tx we get a maximum matchingMy ofG−y. Hence
My ∪ {xy} is a matching of G, which results in µ (G) ≥ µ (G− y) + 1. Therefore, using
Lemma 2.3 and having in mind that G− y is a forest of order n− 1, we get the following
contradiction
n− 1 = α(G) + µ (G) ≥ α(G− y) + µ (G− y) + 1 = n− 1 + 1 = n,
that completes the proof.
V. E. Levit and E. Mandrescu: On the core of a unicyclic graph 329
Remark 2.9. The converse of Lemma 2.8 is not generally true; e.g., the graph H1 from
Figure 3 is a unicyclic König-Egerváry graph, while both c /∈ core(Tc) = {a, b}, and
d /∈ core(Td) = ∅.
Theorem 2.10. If G is a unicyclic non-König-Egerváry graph, then
core (G) = ∪{core (Tx) : x ∈ N1(C)} .
Proof. Claim 1. Every maximum independent set of Tx may be enlarged to some maximum
independent set of G, for each x ∈ N1(C).
Let A ∈ Ω(Tx), y ∈ N (x) ∩ V (C), and z ∈ N (y) ∩ V (C). According to Lemma
2.5, the edge yz is α-critical. Hence there exist Sy ∈ Ω(G), Syz ∈ Ω(G − yz), such that
y ∈ Sy and y, z ∈ Syz .
Case 1. Assume that x /∈ A.
If |Sy − V (Tx)| < α(G − Tx) = |S0|, where S0 ∈ Ω (G− Tx), then the set S1 =
S0 ∪ (Sy ∩ V (Tx)) is independent in G, and we get the contradiction
α (G) = |Sy − V (Tx)|+ |Sy ∩ V (Tx)| < |S0|+ |Sy ∩ V (Tx)| = |S1| .
Therefore, we have |Sy − V (Tx)| = α(G − Tx). Then A ∪ (Sy − V (Tx)) ∈ Ω(G),
otherwise we obtain the following contradiction
|Sy − V (Tx)|+ |A| < α(G) ≤ α(G− Tx) + α(Tx) = |Sy − V (Tx)|+ |A| .
Case 2. Assume now that x ∈ A.
Then we have |A| ≥ |Syz ∩ V (Tx)|, because Syz∩V (Tx) is independent in Tx. Hence
we infer
α (G) = |Syz − {y}| ≤ |(Syz − {y} − (Syz ∩ V (Tx))) ∪A| =
= |(Syz − {y} − V (Tx)) ∪A| .
Since W = (Syz − {y} − V (Tx)) ∪ A is independent and its size is α (G) at least,
it follows that W is also a maximum independent set, i.e., we have A ⊆ W ∈ Ω(G), as
needed.
Claim 2. S ∩ V (Tx) ∈ Ω (Tx) for every S ∈ Ω (G) and each x ∈ N1(C).
Let S ∈ Ω (G), and suppose, to the contrary, that A = S ∩ V (Tx) /∈ Ω (Tx). By
Lemma 2.8, x /∈ core(Tx). Thus we can change A for some B ∈ Ω (Tx) not containing
x. The set (S −A) ∪ B is clearly independent in G, and this leads to the contradiction
|(S −A) ∪B| = |S −A|+ |B| > |S| = α(G).
Combining Claims 1 and 2, we infer that:
core (Tx) = ∩{A : A ∈ Ω(Tx)} = ∩{S ∩ V (Tx) : S ∈ Ω(G)}
= (∩{S : S ∈ Ω(G)}) ∩ V (Tx) = core (G) ∩ V (Tx) ,
which clearly implies
core (G) = ∪{core (Tx) : x ∈ N(V (C))− V (C)}
as required.
330 Ars Math. Contemp. 5 (2012) 325–331
Remark 2.11. The assertion in Theorem 2.10 may fail for:
(i) bipartite unicyclic graphs; for example, the graphs H1, H2 from Figure 4 satisfy
core (H1) = ∪{core (Tx) : x ∈ N1(C)} , and
core (H2) 6= {x, z} = ∪{core (Tx) : x ∈ N1(C)} ;
w w w w w
w w w w
a
b
H1 w w w w
w w w w
@
@
@
x
y
z
t
H2
Figure 4: H1, H2 are bipartite unicyclic graphs, core(H1) = {a, b}, core(H2) =
{t, x, y, z}.
(ii) non-bipartite König-Egerváry unicyclic graphs; for instance,
core (G2) 6= {t, z} = ∪{core (Tx) : x ∈ N1(C)} , while
core (G1) = ∪{core (Tx) : x ∈ N1(C)} ,
where G1 and G2 are from Figure 5.
w w w w w w
w w w
@
@
@
a
b
c
G1 w w w w w
w w



t y z
G2
Figure 5: G1, G2 are König-Egerváry graphs, core(G1) = {a, b, c}, core(G2) = {t, y, z}.
It is worth mentioning that the problem of whether there are vertices in a given graph
G belonging to core (G) is NP-hard [2]. In [17] we have presented both sequential and
parallel algorithms finding core (G) in polynomial time for König-Egerváry graphs. By
Theorem 2.10, a unicyclic graph is either a König-Egerváry graph or its core (G) equals a
union of cores of a finite number of some special subtrees. Therefore, we get the following.
Corollary 2.12. IfG is a unicyclic graph, then core (G) is computable in polynomial time.
3 Conclusions
The main purpose of this paper is to investigate the structure of core (G) for unicyclic
graphs. One the one hand, we have succeeded to represent core (G) as the union of cores
of some specific subtrees of a non König-Egerváry unicyclic graph G. On the other hand,
it is still not clear if there exists a characterization of this kind for bipartite unicyclic graphs
and/or non-bipartite König-Egerváry graphs.
References
[1] F. Belardo, M. Li, M. Enzo, S. K. Simić and J. Wang, On the spectral radius of unicyclic graphs
with prescribed degree sequence, Linear Algebra Appl. 432 (2010), 2323–2334.
V. E. Levit and E. Mandrescu: On the core of a unicyclic graph 331
[2] E. Boros, M. C. Golumbic and V. E. Levit, On the number of vertices belonging to all maximum
stable sets of a graph, Discrete Appl. Math. 124 (2002), 17–25.
[3] R. W. Deming, Independence numbers of graphs - an extension of the König-Egerváry theorem,
Discrete Math. 27 (1979), 23–33.
[4] Z. Du, B. Zhou and N. Trinajstić, Minimum sum-connectivity indices of trees and unicyclic
graphs of a given matching number, J. Math. Chem. 47 (2010), 842–855.
[5] E. Egerváry, On combinatorial properties of matrices, Matematikai Lapok 38 (1931), 16–28.
[6] F. Gavril, Testing for equality between maximum matching and minimum node covering, In-
form. Process. Lett. 6 (1977), 199–202.
[7] B. Huo, S. Ji and X. Li, Note on unicyclic graphs with given number of pendent vertices and
minimal energy, Linear Algebra Appl. 433 (2010), 1381–1387.
[8] D. König, Graphen und Matrizen, Matematikai Lapok 38 (1931), 116–119.
[9] E. Korach, T. Nguyen and B. Peis, Subgraph characterization of red/blue-split graphs and
König-Egerváry graphs, Proceedings of the Seventeenth Annual ACM-SIAM Symposium on
Discrete Algorithms, ACM Press, 2006, pp. 842–850.
[10] C. E. Larson, The critical independence number and an independence decomposition, Eur. J.
Combin. 32 (2011), 294–300.
[11] V. E. Levit and E. Mandrescu, Combinatorial properties of the family of maximum stable sets
of a graph, Discrete Appl. Math. 117 (2002), 149–161.
[12] V. E. Levit and E. Mandrescu, On α+-stable König-Egerváry graphs, Discrete Math. 263
(2003), 179–190.
[13] V. E. Levit and E. Mandrescu, On α-critical edges in König-Egervary graphs, Discrete Math.
306 (2006), 1684–1693.
[14] V. E. Levit and E. Mandrescu, Greedoids on vertex sets of unicycle graphs, Congressus Numer-
antium 197 (2009), 183–191.
[15] V. E. Levit and E. Mandrescu, A characterization of König-Egerváry graphs using a common
property of all maximum matchings, Electronic Notes in Discrete Math. 38 (2011), 565–570.
[16] V. E. Levit and E. Mandrescu, Critical independent sets and König-Egerváry graphs, Graph.
Combinator. 28 (2012), 243–250.
[17] V. E. Levit and E. Mandrescu, An algorithm computing the core of a König-Egerváry graph,
2011, arXiv:1102.1141 [cs.DM], 8 pp.
[18] J. Li, J. Guo and W. C. Shiu, The smallest values of algebraic connectivity for unicyclic graphs,
Discrete Appl. Math. 158 (2010), 1633–1643.
[19] F. Sterboul, A characterization of the graphs in which the transversal number equals the match-
ing number, J. Comb. Theory B 27 (1979), 228–229.
[20] Y. Wu and J. Shu, The spread of the unicyclic graphs, Eur. J. Combin. 31 (2010), 411–418.
[21] M. Zhai, R. Liu and J. Shu, Minimizing the least eigenvalue of unicyclic graphs with fixed
diameter, Discrete Math. 310 (2010), 947–955.