Search

Let G be a simple graph with vertex set V ( G ) . A set S ⊆ V ( G ) is independent if no two vertices from S are adjacent. The graph G is known to be König–Egerváry if α ( G ) + μ ( G ) = | V ( G ) | , where α ( G ) denotes the size of a maximum independent set and μ ( G ) is the cardinality of a maximum matching. A nonempty collection Γ of maximum independent sets is König–Egerváry if | ⋃ Γ | + | ⋂ Γ | = 2 α ( G ) (Jarden et al., 2015). In this paper, we prove that G is a König–Egerváry graph if and only if for every two maximum independent sets S 1 , S 2 of G , there is a matching from V ( G ) − S 1 ∪ S 2 into S 1 ∩ S 2 . Moreover, the same is true, when instead of two sets S 1 and S 2 we consider an arbitrary König–Egerváry collection. [ABSTRACT FROM AUTHOR]

Let G be a graph. A set S of vertices in G dominates the graph if every vertex of G is either in S or a neighbor of a vertex in S . Finding a minimum cardinality set which dominates the graph is an NP -complete problem. The graph G is well-dominated if all its minimal dominating sets are of the same cardinality. The complexity status of recognizing well-dominated graphs is not known. We show that recognizing well-dominated graphs can be done polynomially for graphs without cycles of lengths 4 and 5 , by proving that a graph belonging to this family is well-dominated if and only if it is well-covered. Assume that a weight function w is defined on the vertices of G . Then G is w -well-dominated if all its minimal dominating sets are of the same weight. We prove that the set of weight functions w such that G is w -well-dominated is a vector space, and denote that vector space by W W D ( G ) . We show that W W D ( G ) is a subspace of W C W ( G ) , the vector space of weight functions w such that G is w -well-covered. We provide a polynomial characterization of W W D ( G ) for the case that G does not contain cycles of lengths 4 , 5 , and 6 . [ABSTRACT FROM AUTHOR]

Let α ( G ) be the cardinality of a largest independent set in graph G . If s k is the number of independent sets of size k in G , then I ( G ; x ) = s 0 + s 1 x + ⋯ + s α x α , α = α ( G ) , is the independence polynomial of G (Gutman and Harary, 1983). I ( G ; x ) is palindromic if s α − i = s i for each i ∈ { 0 , 1 , … , ⌊ α / 2 ⌋ } . The corona of G and H is the graph G ∘ H obtained by joining each vertex of G to all the vertices of a copy of H (Frucht and Harary, 1970). In this paper, we show that I ( G ∘ H ; x ) is palindromic for every graph G if and only if H = K r − e , r ≥ 2 . In addition, we connect realrootness of I ( G ∘ H ; x ) with the same property of both I ( G ; x ) and I ( H ; x ) . [ABSTRACT FROM AUTHOR]

Abstract: We verify the conjectures of Mahadev–Peled–Sun and of Orlin, both related to equistable graphs, for the classes of simplicial, very well-covered and line graphs. Our results are based on the combinatorial features of triangle graphs and general partition graphs. In particular, we obtain several equivalent characterizations of equistable simplicial graphs, equistable very well-covered graphs, and equistable line graphs, some of which imply polynomial time recognition algorithms for graphs in these classes. [Copyright &y& Elsevier]

A set is independent in a graph if no two vertices from are adjacent. The independence number is the cardinality of a maximum independent set, while is the cardinality of a maximum matching in . If , then is a König–Egerváry graph. The number is the critical difference of (Zhang, 1990) [22], where . By core (corona ) we denote the intersection (union, respectively) of all maximum independent sets, and by we mean the intersection of all critical sets. A connected graph having only one cycle is called unicyclic. It is known that the relation core holds for every graph (Levit, 2012) [14], while the equality is true for bipartite graphs (Levit, 2013) [15]. For König–Egerváry unicyclic graphs, the difference may equal any non-negative integer. In this paper we prove that if is a non-König–Egerváry unicyclic graph, then: (i) and (ii) . Pay attention that holds for every König–Egerváry graph (Levit, 2011) [11]. [ABSTRACT FROM AUTHOR]

For a graph let , and denote its independence number, matching number, and vertex cover number, respectively. If or, equivalently, , then is a König–Egerváry graph. In this paper we give a new characterization of König–Egerváry graphs. [ABSTRACT FROM AUTHOR]

Abstract: Let . A set is independent if no two vertices from are adjacent, and by we mean the family of all the independent sets of . The number is the difference of , and is critical if [18]. Let us recall the following definitions: Recently, it was established that is true for every graph [12], while the corresponding equality holds for bipartite graphs [13]. In this paper, we present various structural properties of . The main finding claims that [Copyright &y& Elsevier]

Abstract: A maximum stable setin a graph is a stable set of maximum cardinality. The set is called a local maximum stable set of , and we write , if is a maximum stable set of the subgraph induced by the closed neighborhood of . A greedoid is called a local maximum stable set greedoid if there exists a graph such that . Nemhauser and Trotter Jr. (1975) proved that any is a subset of a maximum stable set of . In Levit and Mandrescu (2002) we showed that the family of a forest forms a greedoid on its vertex set. The cases where is bipartite, triangle-free, and well-covered while is a greedoid were analyzed in Levit and Mandrescu (2004) , Levit and Mandrescu (2007) , and Levit and Mandrescu (2008) , respectively. In this paper we demonstrate that if is a very well-covered graph, then the family is a greedoid if and only if has a unique perfect matching. [Copyright &y& Elsevier]

Abstract: A maximum stable set in a graph is a stable set of maximum cardinality. is a local maximum stable set of , and we write , if is a maximum stable set of the subgraph induced by , where is the neighborhood of . A greedoid is called a local maximum stable set greedoid if there exists a graph such that . Nemhauser and Trotter Jr. (1975) , proved that any is a subset of a maximum stable set of . In Levit and Mandrescu (2002) we have shown that the family of a forest forms a greedoid on its vertex set. The cases where is bipartite, triangle-free, well-covered, unicycle, while is a greedoid, were analyzed in Levit and Mandrescu (2004, 2007, 2008, 2001, 2009) , respectively. In this paper, we demonstrate that if the family satisfies the accessibility property, then, first, is a greedoid, and, second, this greedoid, which we called the local maximum stable set greedoid defined by , is an interval greedoid. We also characterize those graphs whose families of local maximum stable sets are either antimatroids or matroids. For these cases, some polynomial recognition algorithms are suggested. [Copyright &y& Elsevier]

Let G = (V, E) be a graph. A set S⊆V is independent if no two vertices from are adjacent, while core(G) is the intersection of all maximum independent sets [V. E. Levit and E. Mandrescu, Discrete Appl. Math., 117 (2002), pp. 149-161]. The independence number α(G)is the cardinality of a largest independent set, and µ(G) is the size of a maximum matching of G. The neighborhood of A⊆V is N(A)= {v ∈ V : N(v)∩=0. The number dc(G)=max{|X|-|N(X)| : X ⊆ V} is called the critical di?erence of G, and is critical if |A|-|N(A)| = dc(G) [C. Q. Zhang, SIAM J. Discrete Math., 3 (1990), pp. 431-438]. We define ker(G) as the intersection of all critical sets. In this paper we prove that if dc(G) ≥ 1, then ker(G) ⊆ core(G) and |ker(G)| >dc(G) ≥ α(G)-µ(G). [ABSTRACT FROM AUTHOR]

Abstract: The independence number of a graph G, denoted by , is the cardinality of an independent set of maximum size in G, while is the size of a maximum matching in G, i.e., its matching number. G is a König–Egerváry graph if its order equals . In this paper we give a new characterization of König–Egerváry graphs. We also deduce some properties of vertices belonging to all maximum independent sets of a König–Egerváry graph. [Copyright &y& Elsevier]

Abstract: The path spectrum of a graph is the set of lengths of all maximal paths in the graph. A set S of positive lengths is tree spectral if it is the path spectrum of a tree. We show that for each even integer at least 34.57% of all subsets of the set are tree spectral, and for each odd integer at least 27.44% of all subsets of the set are tree spectral. [Copyright &y& Elsevier]

We investigate the structure of mincuts in an n-vertex generalized Fibonacci graph of degree 3 and show that the number |CF_{3}(n)| of mincuts in this graph is equal to | {CF}_{3}(n-1)| + | CF_{3}(n-2)| +| CF_{3}(n-3)| - | CF _{3}(n-4)| -| CF_{3}(n-5)| +1. [ABSTRACT FROM AUTHOR]

An independent set in a graph is a set of pairwise non-adjacent vertices, and α(G) is the size of a maximum independent set in the graph G. A matching is a set of non-incident edges, while µ(G) is the cardinality of a maximum matching. If sκ is the number of independent sets of size k in G, then I(G; x) = s0 + s1x + s2x² + … + sαxα, α = α(G), is called the independence polynomial of G (Gutman and Harary, 1986). If sj = sα-j for all 0 ≤ j ≤ ⌊α/2⌋, then I(G; x) is called symmetric (or palindromic). It is known that the graph G º 2K1, obtained by joining each vertex of G to two new vertices, has a symmetric independence polynomial (Stevanović, 1998). In this paper we develop a new algebraic technique in order to take care of symmetric independence polynomials. On the one hand, it provides us with alternative proofs for some previously known results. On the other hand, this technique allows to show that for every graph G and for each non-negative integer k ≤ µ (G), one can build a graph H, such that: G is a subgraph of H, I (H; x) is symmetric, and I (G º 2K1; x) = (1 + x)κ • I (H; x). [ABSTRACT FROM AUTHOR]

Abstract: A graph is well-covered if every maximal independent set has the same cardinality. The recognition problem of well-covered graphs is known to be co-NP-complete. Let be a linear set function defined on the vertices of . Then is -well-covered if all maximal independent sets of are of the same weight. The set of weight functions for which a graph is -well-covered is a vector space. We prove that finding the vector space of weight functions under which an input graph is -well-covered can be done in polynomial time, if the input graph contains neither nor nor nor . [ABSTRACT FROM AUTHOR]

Abstract: is a local maximum stable set of a graph , and we write , if the set is a maximum stable set of the subgraph induced by , where is the neighborhood of . In Levit and Mandrescu (2002) we have proved that is a greedoid for every forest . The cases of bipartite graphs and triangle-free graphs were analyzed in Levit and Mandrescu (2003) and Levit and Mandrescu (2007) respectively. In this paper we give necessary and sufficient conditions for to form a greedoid, where is: [(a)] the disjoint union of a family of graphs; [(b)] the Zykov sum of a family of graphs; [(c)] the corona obtained by joining each vertex of a graph to all the vertices of a graph . [Copyright &y& Elsevier]

Abstract: The stability number of a graph G, denoted by , is the cardinality of a stable set of maximum size in G. If , then e is an -critical edge, and if , then e is a -critical edge, where is the cardinality of a maximum matching in G. G is a König–Egerváry graph if its order equals . Beineke, Harary and Plummer have shown that the set of -critical edges of a bipartite graph forms a matching. In this paper we generalize this statement to König–Egerváry graphs. We also prove that in a König–Egerváry graph -critical edges are also -critical, and that they coincide in bipartite graphs. For König–Egerváry graphs, we characterize -critical edges that are also -critical. Eventually, we deduce that holds for any tree T, and describe the König–Egerváry graphs enjoying this property, where is the number of -critical vertices and is the number of -critical edges. [Copyright &y& Elsevier]

Abstract: We define a two-terminal directed acyclic graph (st-dag) characterized by a special structure of its mincuts and call it a nested graph. It is proved that every nested graph is series-parallel as well. We show that an st-dag of order n has exactly mincuts if and only if it is nested. [Copyright &y& Elsevier]

Abstract: A matching M is called uniquely restricted in a graph G if it is the unique perfect matching of the subgraph induced by the vertices that M saturates. G is a unicycle graph if it owns only one cycle. Golumbic, Hirst and Lewenstein observed that for a tree or a graph with only odd cycles the size of a maximum uniquely restricted matching is equal to the matching number of the graph. In this paper we characterize unicycle graphs enjoying this equality. Moreover, we describe unicycle graphs with only uniquely restricted maximum matchings. Using these findings, we show that unicycle graphs having only uniquely restricted maximum matchings can be recognized in polynomial time. [Copyright &y& Elsevier]

A maximum stable set in a graph G is a stable set of maximum size. S is a local maximum stable set of G, and we write S∈Ψ(G), if S is a maximum stable set of the subgraph spanned by S∪N(S), where N(S) is the neighborhood of S. A matching M is uniquely restricted if its saturated vertices induce a subgraph which has a unique perfect matching, namely M itself. Nemhauser and Trotter Jr. (Math. Programming 8(1975) 232–248), proved that any S∈Ψ(G) is a subset of a maximum stable set of G. In Levit and Mandrescu (Discrete Appl. Math., 124 (2002) 91–101) we have shown that the family Ψ(T) of a forest T forms a greedoid on its vertex set. In this paper, we demonstrate that for a bipartite graph G, Ψ(G) is a greedoid on its vertex set if and only if all its maximum matchings are uniquely restricted. [Copyright &y& Elsevier]

A maximum stable set in a graph G is a stable set of maximum cardinality. S is a local maximum stable set if it is a maximum stable of the subgraph of G spanned by S∪N(S), where N(S) is the neighborhood of S. One theorem of Nemhauser and Trotter Jr. (Math. Programming 8 (1975) 232–248), working as a useful sufficient local optimality condition for the weighted maximum stable set problem, ensures that any local maximum stable set of G can be enlarged to a maximum stable set of G. In this paper we demonstrate that an inverse assertion is true for forests. Namely, we show that for any non-empty local maximum stable set S of a forest T there exists a local maximum stable set S1 of T, such that S1⊂S and |S1|=|S|−1. Moreover, as a further strengthening of both the theorem of Nemhauser and Trotter Jr. and its inverse, we prove that the family of all local maximum stable sets of a forest forms a greedoid on its vertex set. [Copyright &y& Elsevier]

Abstract: If denotes the number of independent sets of cardinality and is the size of a maximum independent set in graph , then is the independence polynomial of (Gutman and Harary, 1983) . In this paper we provide an elementary proof of the inequality (Engström, 2009) , where is the decycling number of (Beineke and Vandell, 1997) , namely, the minimum number of vertices that have to be deleted in order to turn into a forest. [Copyright &y& Elsevier]

Berge’s Lemma says that for each independent set S and maximum independent set X , there is a matching from S − X into X − S , namely, a function of S − X into X − S such that ( s , f ( s ) ) is an edge for each s ∈ S − X . Levit and Mandrescu prove A Set and Collection Lemma. It is a strengthening of Berge’s Lemma, by which one can obtain a matching M : S − ⋂ Γ → ⋃ Γ − S , where S is an independent set and Γ is a collection of maximum independent sets. Jarden, Levit and Mandrescu invoke new inequalities from A Set and Collection Lemma and yield a new characterization of König–Egerváry graphs. In the current paper, we study Berge systems (collections of vertex sets, where the conclusion of Berge’s Lemma hold). The work is divided into two parts: the general theory of Berge systems and Berge systems associated with groups (or more precisely, in non-commuting graphs). We first show that there exists many Berge systems. The notion of an ideal is central in several branches of mathematics. We define ‘a graph ideal’, which is a natural generalization of ‘an ideal’ in the context of graph theory. We show that every graph ideal carries a Berge system. We prove a sufficient condition for a Berge system to be a multi-matching system (collections where the conclusion of a Set and Collection Lemma holds). We get new inequalities in multi-matching systems. Here, we do a turn about from the general theory of Berge systems into the study of Berge systems in non-commuting graphs. We prove that for every group G , if A and B are maximal abelian subsets of 〈 A , B 〉 G and | A | ≤ | B | , then there is a non-commutative matching of A − B into B − A . It means that every non-commuting graph carries a Berge system. Moreover, we apply the sufficient condition to get a multi-matching system in the context of non-commuting graphs and invoke new inequalities in group theory. Surprisingly, the new results concerning groups, do not hold for rings. [ABSTRACT FROM AUTHOR]