Search

The independence number $\alpha(G)$ is the cardinality of a maximum independent set, while $\mu(G)$ is the size of a maximum matching in $G$. If $\alpha(G)+\mu(G)$ equals the order of $G$, then $G$ is called a Konig-Egervary graph. The number $d\left( G\right) =\max\{\left\vert A\right\vert -\left\vert N\left( A\right) \right\vert :A\subseteq V\}$ is called the critical difference of $G$ (where $N\left( A\right) =\left\{ v:v\in V,N\left( v\right) \cap A\neq\emptyset\right\} $). It is known that $\alpha(G)-\mu(G)\leq d\left( G\right) $ holds for every graph. A graph $G$ is unicyclic if it has a unique cycle and almost bipartite if it has only one odd cycle. Let $\mathrm{\ker}(G)=\bigcap\left\{ S:S\text{ is a critical independent set}\right\} $, $\mathrm{core}\left( G\right) $ be the intersection of all maximum independent sets, and $\mathrm{corona}\left( G\right) $ be the union of all maximum independent sets of $G$. It is known that $\mathrm{\ker}(G)\subseteq\mathrm{core}(G)$ is true for every graph, while the equality holds for bipartite graphs, and for unicyclic non-Konig-Egervary graphs. In this paper, we prove that if $G$ is an almost bipartite non-Konig-Egervary graph, then $\mathrm{\ker}(G)=$ $\mathrm{core}(G)$, $\mathrm{corona}(G)$ $\cup$ $N(\mathrm{core} \left( G\right) )=V(G)$, and $\left\vert \mathrm{corona}(G)\right\vert +\left\vert \mathrm{core}(G)\right\vert =2\alpha(G)+1$., Comment: 12 pages, 7 figures. arXiv admin note: text overlap with arXiv:1905.09462

Let $G$ be a simple graph with vertex set $V\left( G\right) $. A set $S\subseteq V\left( G\right) $ is independent if no two vertices from $S$ are adjacent, and by $\mathrm{Ind}(G)$ we mean the family of all independent sets of $G$. The number $d\left( X\right) =$ $\left\vert X\right\vert -\left\vert N(X)\right\vert $ is the difference of $X\subseteq V\left( G\right) $, and a set $A\in\mathrm{Ind}(G)$ is critical if $d(A)=\max \{d\left( I\right) :I\in\mathrm{Ind}(G)\}$ (Zhang, 1990). Let us recall the following definitions: $\mathrm{core}\left( G\right) $ = $\bigcap$ {S : S is a maximum independent set}. $\mathrm{corona}\left( G\right)$ = $\bigcup$ {S :S is a maximum independent set}. $\mathrm{\ker}(G)$ = $\bigcap$ {S : S is a critical independent set}. $\mathrm{diadem}(G)$ = $\bigcup$ {S : S is a critical independent set}. In this paper we present various structural properties of $\mathrm{\ker}(G)$, in relation with $\mathrm{core}\left( G\right) $, $\mathrm{corona}\left( G\right) $, and $\mathrm{diadem}(G)$., 15 pages; 12 figures. arXiv admin note: substantial text overlap with arXiv:1102.1138

Let alpha(G) denote the maximum size of an independent set of vertices and mu(G) be the cardinality of a maximum matching in a graph G. A matching saturating all the vertices is perfect. If alpha(G) + mu(G) equals the number of vertices of G, then it is called a Konig-Egervary graph. A graph is unicyclic if it has a unique cycle. In 2010, Bartha conjectured that a unique perfect matching, if it exists, can be found in O(m) time, where m is the number of edges. In this paper we validate this conjecture for Konig-Egervary graphs and unicylic graphs. We propose a variation of Karp-Sipser leaf-removal algorithm (Karp and Spiser, 1981), which ends with an empty graph if and only if the original graph is a Konig-Egervary graph with a unique perfect matching obtained as an output as well. We also show that a unicyclic non-bipartite graph G may have at most one perfect matching, and this is the case where G is a Konig-Egervary graph., Comment: 10 pages, 5 figures

A set S of vertices is independent in a graph G if no two vertices from S are adjacent, and alpha(G) is the cardinality of a maximum independent set of G. G is called a Konig-Egervary graph if its order equals alpha(G)+mu(G), where mu(G) denotes the size of a maximum matching. By core(G) we mean the intersection of all maximum independent sets of G. To decide whether core(G) is empty is known to be NP-hard. In this paper, we present some polynomial time algorithms finding core(G) of a Konig-Egervary graph G., 8 pages, 5 figures

Let G=(V,E) be a graph. A set S is independent if no two vertices from S are adjacent. The independence number alpha(G) is the cardinality of a maximum independent set, and mu(G) is the size of a maximum matching. The number id_{c}(G)=max{|I|-|N(I)|:I is an independent set} is called the critical independence difference of G, and A is critical if |A|-|N(A)|=id_{c}(G). We define core(G) as the intersection of all maximum independent sets, and ker(G)as the intersection of all critical independent sets. In this paper we prove that if a graph G is non-quasi-regularizable (i.e., there exists some independent set A, such that |A|>|N(A)|), then: ker(G) is a subset of core(G), and |ker(G)|> id_{c}(G) >= alpha(G)-mu(G) > 0., 9 pages; 4 figures

The square of a graph G is the graph G^2 with the same vertex set as in G, and an edge of G^2 is joining two distinct vertices, whenever the distance between them in G is at most 2. G is a square-stable graph if it enjoys the property alpha(G)=alpha(G^2), where alpha(G) is the size of a maximum stable set in G. In this paper we show that G^2 is a Konig-Egervary graph if and only if G is a square-stable Konig-Egervary graph., 6 pages, 4 figures

The independence number of a graph G, denoted by alpha(G), is the cardinality of an independent set of maximum size in G, while mu(G) is the size of a maximum matching in G, i.e., its matching number. G is a Konig-Egervary graph if its order equals alpha(G)+mu(G). In this paper we give a new characterization of Konig-Egervary graphs. We also deduce some properties of vertices belonging to all maximum independent sets of a Konig-Egervary graph., 9 pages, 5 figures

Let alpha(G) be the cardinality of a independence set of maximum size in the graph G, while mu(G) is the size of a maximum matching. G is a Konig--Egervary graph if its order equals alpha(G) + mu(G). The set core(G) is the intersection of all maximum independent sets of G (Levit & Mandrescu, 2002). The number def(G)=|V(G)|-2*mu(G) is the deficiency of G (Lovasz & Plummer, 1986). The number d(G)=max{|S|-|N(S)|:S in Ind(G)} is the critical difference of G. An independent set A is critical if |A|-|N(A)|=d(G), where N(S) is the neighborhood of S (Zhang, 1990). In 2009, Larson showed that G is Konig--Egervary graph if and only if there exists a maximum independent set that is critical as well. In this paper we prove that: (i) d(G)=|core(G)|-|N(core(G))|=alpha(G)-mu(G)=def(G) for every Konig--Egervary graph G; (ii) G is Konig--Egervary graph if and only if every maximum independent set of G is critical., 8 pages, 5 figures

The stability number of a graph G, denoted by alpha(G), is the cardinality of a maximum stable set, and mu(G) is the cardinality of a maximum matching in G. If alpha(G)+mu(G) equals its order, then G is a Konig-Egervary graph. In this paper we deal with square-stable graphs, i.e., the graphs G enjoying the equality alpha(G)=alpha(G^{2}), where G^{2} denotes the second power of G. In particular, we show that a Konig-Egervary graph is square-stable if and only if it has a perfect matching consisting of pendant edges, and in consequence, we deduce that well-covered trees are exactly the square-stable trees., Comment: 12 pages, 9 figures

A maximum stable set in a graph G is a stable set of maximum cardinality. S is a local maximum stable set of G, if S is a maximum stable set of the subgraph induced by its closed neighborhood. It is known that the family of all local maximum stable sets of a forest forms a greedoid on its vertex set. Bipartite, triangle-free, and well-covered graphs whose families of local maximum stable sets form greedoids have been analyzed as well. A unicycle graph owns only one cycle. In this paper we characterize the unicycle graphs whose families of local maximum stable sets form greedoids., Comment: 9 pages; 4 figures

If alpha=alpha(G) is the maximum size of an independent set and s_{k} equals the number of stable sets of cardinality k in graph G, then I(G;x)=s_{0}+s_{1}x+...+s_{alpha}x^{alpha} is the independence polynomial of G. In this paper we prove that: 1. I(T;-1) equels either -1 or 0 or 1 for every tree T; 2. I(G;-1)=0 for every connected well-covered graph G of girth > 5, non-isomorphic to C_{7} or K_{2}; 3. the absolute value of I(G;-1) is not greater than 2^nu(G), for every graph G, where nu(G) is its cyclomatic number., 16 pages; 13 figures

G is a Koenig-Egervary graph provided alpha(G)+ mu(G)=|V(G)|, where mu(G) is the size of a maximum matching and alpha(G) is the cardinality of a maximum stable set. S is a local maximum stable set of G if S is a maximum stable set of the closed neighborhood of S. Nemhauser and Trotter Jr. proved that any local maximum stable set is a subset of a maximum stable set of G. In this paper we demonstrate that if S is a local maximum stable set, the subgraph H induced by the closed neighborhood of S is a Koenig-Egervary graph, and M is a maximum matching in H, then M is a local maximum stable set in the line graph of G., 7 pages; 7 figures

A maximum stable set in a graph G is a stable set of maximum cardinality. S is a local maximum stable set of G, if S is a maximum stable set of the subgraph induced by its closed neighborhood. Nemhauser and Trotter Jr. proved in 1975 that any local maximum stable set is a subset of a maximum stable set of G. In 2002 we showed that the family of all local maximum stable sets of a forest forms a greedoid on its vertex set. The cases where G is bipartite, triangle-free, well-covered, while the family of all local maximum stable sets is a greedoid, were analyzed in 2004, 2007, and 2008, respectively. In this paper we demonstrate that if the family of all local maximum stable sets of the graph satisfies the accessibility property, then it is an interval greedoid. We also characterize those graphs whose families of local maximum stable sets are either antimatroids or matroids., Comment: 13 pages, 11 figures

If for any $k$ the $k$-th coefficient of a polynomial $I(G;x)$ is equal to the number of stable sets of cardinality $k$ in the graph $G$, then it is called the independence polynomial of $G$ (Gutman and Harary, 1983). Alavi, Malde, Schwenk and Erdos (1987) conjectured that $I(G;x)$ is unimodal, whenever $G$ is a forest, while Brown, Dilcher and Nowakowski (2000) conjectured that $I(G;x)$ is unimodal for any well-covered graph G. Michael and Traves (2003) showed that the assertion is false for well-covered graphs with $a(G)$ > 3 ($a(G)$ is the size of a maximum stable set of the graph $G$), while for very well-covered graphs the conjecture is still open. In this paper we give support to both conjectures by demonstrating that if $a(G)$ < 4, or $G$ belongs to ${K_{1,n}, P_{n}: n > 0}$, then $I(G*;x)$ is log-concave, and, hence, unimodal (where $G*$ is the very well-covered graph obtained from $G$ by appending a single pendant edge to each vertex)., 8 pages, 4 figures

If for any $k$ the $k$-th coefficient of a polynomial I(G;x) is equal to the number of stable sets of cardinality $k$ in the graph $G$, then it is called the independence polynomial of $G$ (Gutman and Harary, 1983). Let $a$ be the size of a maximum stable set. Alavi, Malde, Schwenk and Erdos (1987)conjectured that I(T,x) is unimodal for any tree T, while, in general, they proved that for any permutation $p$ of {1,2,...,a} there is a graph such that s_{p(1)}=...>=s_{a-1}>=s_{a} are valid for any (a) bipartite graph $G$; (b) quasi-regularizable graph $G$ on $2a$ vertices. In particular, we infer that this is true for (a) trees, thus doing a step in an attempt to prove Alavi et al.' conjecture; (b) very well-covered graphs. Consequently, for this case, the unconstrained subsequence appearing in the roller-coaster conjecture can be shorten to (s_{a/2},s_{a/2+1},...,s_{(2a-1)/3}). We also show that the independence polynomial of a very well-covered graph $G$ is unimodal for a, Comment: 10 pages, 4 figures

If for any $k$ the $k$-th coefficient of a polynomial I(G;x) is equal to the number of stable sets of cardinality $k$ in graph $G$, then it is called the independence polynomial of $G$ (Gutman and Harary, 1983). J. I. Brown, K. Dilcher and R. J. Nowakowski (2000) conjectured that the independence polynomial of a well-covered graph $G$ (i.e., a graph whose all maximal independent sets are of the same size) is unimodal, that is, there exists an index $k$ such that the part of the sequence of coefficients from the first to $k$-th is non-decreasing while the other part of coefficients is non-increasing. T. S. Michael and N. Traves (2002) provided examples of well-covered graphs whose independence polynomials are not unimodal. A. Finbow, B. Hartnell and R. J. Nowakowski (1993) proved that under certain conditions, any well-covered graph equals G* for some $G$, where G* is the graph obtained from $G$ by appending a single pendant edge to each vertex of $G$. Y. Alavi, P. J. Malde, A. J. Schwenk and P. Erd\"{o}s (1987) asked whether for trees the independence polynomial is unimodal. V. E. Levit and E. Mandrescu (2002) validated the unimodality of the independence polynomials of some well-covered trees (e.g., $P_{n}^{*},K_{1,n}^{*}$, where $P_{n}$ is the path on $n$ vertices and $K_{1,n}$ is the $n$-star graph). In this paper we show that for any graph $G$ with the stability number alpha(G) < 5, the independence polynomial of G* is unimodal., Comment: This paper has been presented at Thirty-fourth Southeastern International Conference on Combinatorics, Graph Theory, and Computing, March 2003, Florida Atlantic University, USA; 13 pages; 2 figures

The number of stable sets of cardinality $k$ in graph $G$ is the $k$-th coefficient of the independence polynomial of $G$ (I. Gutman and F. Harary, 1983). In 1990, Y. O. Hamidoune proved that for any claw-free graph, its independence polynomial is unimodal, i.e., there exists a coefficient $k$ such that the part of the sequence of coefficients from the first to $k$-th is non-decreasing while the second part of coefficients is non-increasing. Y. Alavi, P. J. Malde, A. J. Schwenk and P. Erd\"{o}s (1987) asked whether for trees (or perhaps forests) the independence polynomial is unimodal. J. I. Brown, K. Dilcher and R. J. Nowakowski (2000) conjectured that it is true for any well-covered graph (a graph whose all maximal independent sets have the same size). V. E. Levit and E. Mandrescu (1999) demonstrated that every well-covered tree can be obtained as a join of a number of well-covered spiders, where a spider is a tree having at most one vertex of degree at least three. In this paper we show that the independence polynomial of any well-covered spider is unimodal. In addition, we introduce some graph transformations respecting independence polynomials. They allow us to reduce several types of well-covered trees to claw-free graphs, and, consequently, to prove that their independence polynomials are unimodal., Comment: A preliminary version of this paper was presented at Second Haifa Workshop on Interdisciplinary Applications, of Graph Theory, Combinatorics and Algorithms June 17-20, 2002. 21 pages, 15 figures

A maximum stable set in a graph G is a stable set of maximum size. S is a local maximum stable set if it is a maximum stable set of the subgraph of G spanned by the union of S and 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. One theorem of Nemhauser and Trotter Jr., 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 one of our previous papers it is proven that the family of all local maximum stable sets of a forest forms a greedoid on its vertex set. In this paper we obtain a generalization of this assertion claiming that the family of all local maximum stable sets of a bipartite graph G is a greedoid if and only if all maximum matchings of G are uniquely restricted.

The stability number of a graph G, denoted by alpha(G), is the cardinality of a stable set of maximum size in G. A graph is well-covered if every maximal stable set has the same size. G is a Koenig-Egervary graph if its order equals alpha(G) + mu(G), where mu(G) is the cardinality of a maximum matching in G. In this paper we characterize $��^{++}$-stable graphs, namely, the graphs whose stability numbers are invariant to adding any two edges from their complements. We show that a K��nig-Egerv��ry graph is $��^{++}$-stable if and only if it has a perfect matching consisting of pendant edges and no four vertices of the graph span a cycle. As a corollary it gives necessary and sufficient conditions for $��^{++}$-stability of bipartite graphs and trees. For instance, we prove that a bipartite graph is $��^{++}$-stable if and only if it is well-covered and C4-free., 11 pages, 3 figures

The stability number of a graph G, denoted by alpha(G), is the cardinality of a stable set of maximum size in G. If alpha(G-e) > alpha(G), then e is an alpha-critical edge, and if mu(G-e) < mu(G), then e is a mu-critical edge, where mu(G) is the cardinality of a maximum matching in G. G is a Koenig-Egervary graph if alpha(G) + mu(G) equals its order. Beineke, Harary and Plummer have shown that the set of alpha-critical edges of a bipartite graph is a matching. In this paper we generalize this statement to Koenig-Egervary graphs. We also prove that in a Koenig-Egervary graph alpha-critical edges are also mu-critical, and that they coincide in bipartite graphs. We obtain that for any tree its stability number equals the sum of the cardinality of the set of its alpha-critical vertices and the size of the set of its alpha-critical edges. Eventually, we characterize the Koenig-Egervary graphs enjoying this property., 15 pages, 10 figures

A square (0,1)-matrix X of order n > 0 is called fully indecomposable if there exists no integer k with 0 < k < n, such that X has a k by n-k zero submatrix. A stable set of a graph G is a subset of pairwise nonadjacent vertices. The stability number of G, denoted by $��(G)$, is the cardinality of a maximum stable set in G. A graph is called $��$-stable if its stability number remains the same upon both the deletion and the addition of any edge. We show that a connected bipartite graph has exactly two maximum stable sets that partition its vertex set if and only if its reduced adjacency matrix is fully indecomposable. We also describe a decomposition structure of $��$-stable bipartite graphs in terms of their reduced adjacency matrices. On the base of these findings we obtain both new proofs for a number of well-known theorems on the structure of matrices due to Brualdi, Marcus and Minc, Dulmage and Mendelsohn, and some generalizations of these statements. Several new results on $��$-stable bipartite graphs and their corresponding reduced adjacency matrices are presented, as well. Two kinds of matrix product are also considered (namely, Boolean product and Kronecker product), and their corresponding graph operations. As a consequence, we obtain a strengthening of one Lewin's theorem claiming that the product of two fully indecomposable matrices is a fully indecomposable matrix., A preliminary version of this paper has been presented at the Tenth Haifa Matrix Theory Conference, January 1998, Technion, Haifa, Israel; 16 pages, 5 figures

The stability number of a graph G, denoted by alpha(G), is the cardinality of a maximum stable set, and mu(G) is the cardinality of a maximum matching in G. If alpha(G) + mu(G) equals its order, then G is a Koenig-Egervary graph. We call G an $��$-square-stable graph, shortly square-stable, if alpha(G) = alpha(G*G), where G*G denotes the second power of G. These graphs were first investigated by Randerath and Wolkmann. In this paper we obtain several new characterizations of square-stable graphs. We also show that G is an square-stable Koenig-Egervary graph if and only if it has a perfect matching consisting of pendant edges. Moreover, we find that well-covered trees are exactly square-stable trees. To verify this result we give a new proof of one Ravindra's theorem describing well-covered trees., 13 pages, 6 figures

The stability number of a graph G, is the cardinality of a stable set of maximum size in G. If the stability number of G remains the same upon the addition of any edge, then G is called $��^{+}$-stable. G is a K��nig-Egervary graph if its order equals the sum of its stability number and the cardinality of a maximum matching. In this paper we characterize $��^{+}$-stable K��nig-Egervary graphs, generalizing some previously known results on bipartite graphs and trees. Namely, we prove that a K��nig-Egervary graph is $��^{+}$-stable if and only if either the set of vertices belonging to no maximum stable set is empty, or the cardinality of this set equals one, and G has a perfect matching. Using this characterization we obtain several new findings on general K��nig-Egervary graphs, for example, the equality between the cardinalities of the set of vertices belonging to all maximum stable sets and the set of vertices belonging to no maximum stable set of G is a necessary and sufficient condition for a K��nig-Egervary graph G to have a perfect matching., A preliminary version of this paper has been presented at 9th SIAM Conference on Discrete Mathematics, July 1998, the University of Toronto, Toronto, Canada; 13 pages, 5 figures

The stability number of a graph G is the cardinality of a stability system of G (that is of a stable set of maximum size of G). A graph is alpha-stable if its stability number remains the same upon both the deletion and the addition of any edge. Trying to generalize some stable trees properties, we show that there does not exist any alpha-stable chordal graph, and we prove that: if G is a connected bipartite graph, then the following assertions are equivalent: G is alpha-stable; G can be written as a vertex disjoint union of connected bipartite graphs, each of them having exactly two stability systems covering its vertex set; G has perfect matchings and no edge belongs to all its perfect matchings; from each vertex of G are issuing at least two edges contained in some perfect matchings of G; any vertex of G lies on a cycle, whose edges are alternately in and not in some perfect matching; no vertex belongs to all stability systems of G, and no edge belongs to all its perfect matchings., A preliminary version of this paper has been presented at The Third Krakow Conference On Graph Theory, September 15-19, 1997, Krakow University, Kazimierz Dolny, Poland; 16 pages