Search

Let $G$ be a $\mathbf{W}_{p}$ graph if $n\geq p$ and every $p$ pairwise disjoint independent sets of $G$ are contained within $p$ pairwise disjoint maximum independent sets. In this paper, we establish that every $\mathbf{W}_{p}$ graph $G$ is $p$-quasi-regularizable if and only if $n\geq (p+1)\alpha $, where $\alpha $ is the independence number of $G$. This finding ensures that the independence polynomial of a connected $\mathbf{W}_{p}$ graph $G$ is log-concave whenever $(p+1)\alpha \leq n\leq 2p\alpha +p+1$. Furthermore, we demonstrate that the independence polynomial of the clique corona $G\circ K_{p}$ is invariably log-concave for all $p\geq 1$. As an application, we validate a long-standing conjecture claiming that the independence polynomial of a very well-covered graph is unimodal., Comment: 16 pages, 2 figures

Let $\alpha(G)$ denote the cardinality of a maximum independent set, while $\mu(G)$ be the size of a maximum matching in $G=\left( V,E\right) $. It is known that if $\alpha(G)+\mu(G)=\left\vert V\right\vert $, then $G$ is a K\"{o}nig-Egerv\'{a}ry graph. The critical difference $d(G)$ is $\max\{d(I):I\in\mathrm{Ind}(G)\}$, where $\mathrm{Ind}(G)$\ denotes the family of all independent sets of $G$. If $A\in\mathrm{Ind}(G)$ with $d\left( X\right) =d(G)$, then $A$ is a critical independent set. For a graph $G$, let $\mathrm{diadem}(G)=\bigcup\{S:S$ is a critical independent set in $G\}$, and $\varrho_{v}\left( G\right) $ denote the number of vertices $v\in V\left( G\right) $, such that $G-v$ is a K\"{o}nig-Egerv\'{a}ry graph. A graph is called almost bipartite if it has a unique odd cycle. In this paper, we show that if $G$ is an almost bipartite non-K\"{o}nig-Egerv\'{a}ry graph with the unique odd cycle $C$, then the following assertions are true: 1. every maximum matching of $G$ contains $\left\lfloor {V(C)}/{2}\right\rfloor $ edges belonging to $C$; 2. $V(C)\cup N_{G}\left[ \mathrm{diadem}\left( G\right) \right] =V$ and $V(C)\cap N_{G}\left[ \mathrm{diadem}\left( G\right) \right] =\emptyset$; 3. $\varrho_{v}\left( G\right) =\left\vert \mathrm{corona}\left( G\right) \right\vert -\left\vert \mathrm{diadem}\left( G\right) \right\vert $, where $\mathrm{corona}\left( G\right) $ is the union of all maximum independent sets of $G$; 4. $\varrho_{v}\left( G\right) =\left\vert V\right\vert $ if and only if $G=C_{2k+1}$ for some integer $k\geq1$., Comment: 20 pages, 7 figures. arXiv admin note: text overlap with arXiv:2401.05523

The graph G=(V,E) is called Konig-Egervary if the sum of its independence number and its matching number equals its order. Let RV(G) denote the number of vertices v such that G-v is Konig-Egervary, and let RE(G) denote the number of edges e such that G-e is Konig-Egervary. Clearly, RV(G) = |V| and RE(G) = |E| for bipartite graphs. Unlike the bipartiteness, the property of being a Konig-Egervary graph is not hereditary. In this paper, we present an equality expressing RV(G) in terms of some graph parameters, and a tight inequality bounding RE(G) in terms of the same parameters, when G is Konig-Egervary., Comment: 19 pages, 12 figures

Let $\alpha(G)$ denote the cardinality of a maximum independent set, while $\mu(G)$ be the size of a maximum matching in $G=\left( V,E\right) $. Let $\xi(G)$ denote the size of the intersection of all maximum independent sets. It is known that if $\alpha(G)+\mu(G)=n(G)=\left\vert V\right\vert $, then $G$ is a K\"{o}nig-Egerv\'{a}ry graph. If $\alpha(G)+\mu(G)=n(G) -1$, then $G$ is a $1$-K\"{o}nig-Egerv\'{a}ry graph. If $G$ is not a K\"{o}nig-Egerv\'{a}ry graph, and there exists a vertex $v\in V$ (an edge $e\in E$) such that $G-v$ ($G-e$) is K\"{o}nig-Egerv\'{a}ry, then $G$ is called a vertex (an edge) almost K\"{o}nig-Egerv\'{a}ry graph (respectively). The critical difference $d(G)$ is $\max\{d(I):I\in\mathrm{Ind}(G)\}$, where $\mathrm{Ind}(G)$ denotes the family of all independent sets of $G$. If $A\in\mathrm{Ind}(G)$ with $d\left( X\right) =d(G)$, then $A$ is a critical independent set. Let $diadem (G)=\bigcup\{S:S$ is a critical independent set in $G\}$, and $\varrho_{v}\left( G\right) $ denote the number of vertices $v\in V\left( G\right) $, such that $G-v$ is a K\"{o}nig-Egerv\'{a}ry graph. In this paper, we characterize all types of almost K\"{o}nig-Egerv\'{a}ry graphs and present interrelationships between them. We also show that if $G$ is a $1$-K\"{o}nig-Egerv\'{a}ry graph, then $\varrho_{v}\left( G\right) \leq n\left( G\right) +d\left( G\right) -\xi\left( G\right) -\beta(G)$, where $\beta(G)=\left\vert diadem(G)\right\vert $. As an application, we characterize the $1$-K\"{o}nig-Egerv\'{a}ry graphs that become K\"{o}nig-Egerv\'{a}ry after deleting any vertex., Comment: 17 pages, 10 figures

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

A set $S\subseteq V(G)$ is independent (or stable) if no two vertices from $S$ are adjacent, and by $\mathrm{Ind}(G)$ we mean the set of all independent sets of $G$. A set $A\in\mathrm{Ind}(G)$ is critical (and we write $A\in CritIndep(G)$) if $\left\vert A\right\vert -\left\vert N(A)\right\vert =\max\{\left\vert I\right\vert -\left\vert N(I)\right\vert :I\in \mathrm{Ind}(G)\}$, where $N(I)$ denotes the neighborhood of $I$. If $S\in\mathrm{Ind}(G)$ and there is a matching from $N(S)$ into $S$, then $S$ is a crown, and we write $S\in Crown(G)$. Let $\Psi(G)$ be the family of all local maximum independent sets of graph $G$, i.e., $S\in\Psi(G)$ if $S$ is a maximum independent set in the subgraph induced by $S\cup N(S)$. In this paper we show that $CritIndep(G)\subseteq Crown(G)$ $\subseteq\Psi(G)$ are true for every graph. In addition, we present some classes of graphs where these families coincide and form greedoids or even more general set systems that we call augmentoids., Comment: 19 pages, 11 figures

A set $S\subseteq V$ is \textit{independent} in a graph $G=\left( V,E\right) $ if no two vertices from $S$ are adjacent. The \textit{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 \textit{K\"{o}nig-Egerv\'{a}ry graph }\cite{dem,ster}. 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 \textit{critical difference} of $G$ \cite{Zhang} (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 \cite{Levman2011a,Lorentzen1966,Schrijver2003}. In \cite{LevMan5} it was shown that $d(G)=\alpha(G)-\mu(G)$ is true for every K\"{o}nig-Egerv\'{a}ry graph. A graph $G$ is \textit{(i)} \textit{unicyclic} if it has a unique cycle, \textit{(ii)} \textit{almost bipartite} if it has only one odd cycle. It was conjectured in \cite{LevMan2012a,LevMan2013a} and validated in \cite{Bhattacharya2018} that $d(G)=\alpha(G)-\mu(G)$ holds for every unicyclic non-K\"{o}nig-Egerv\'{a}ry graph $G$. In this paper we prove that if $G$ is an almost bipartite graph of order $n\left( G\right) $, then $\alpha(G)+\mu(G)\in\left\{ n\left( G\right) -1,n\left( G\right) \right\} $. Moreover, for each of these two values, we characterize the corresponding graphs. Further, using these findings, we show that the critical difference of an almost bipartite graph $G$ satisfies \[ d(G)=\alpha(G)-\mu(G)=\left\vert \mathrm{core}(G)\right\vert -\left\vert N(\mathrm{core}(G))\right\vert , \] where by \textrm{core}$\left( G\right) $ we mean the intersection of all maximum independent sets., Comment: 12 pages, 5 figures. arXiv admin note: text overlap with arXiv:1102.4727

Let $\alpha(G)$ denote the cardinality of a maximum independent set, while $\mu(G)$ be the size of a maximum matching in the graph $G=\left(V,E\right) $. If $\alpha(G)+\mu(G)=\left\vert V\right\vert $, then $G$ is a K\"onig-Egerv\'ary graph. If $d_{1}\leq d_{2}\leq\cdots\leq d_{n}$ is the degree sequence of $G$, then the annihilation number $h\left(G\right) $ of $G$ is the largest integer $k$ such that $\sum\limits_{i=1}^{k}d_{i}\leq\left\vert E\right\vert $ (Pepper 2004, Pepper 2009). A set $A\subseteq V$ satisfying $\sum \limits_{a\in A} deg(a)\leq\left\vert E\right\vert $ is an annihilation set, if, in addition, $ deg\left(v\right) +\sum\limits_{a\in A} deg(a)>\left\vert E\right\vert $, for every vertex $v\in V(G)-A$, then $A$ is a maximal annihilation set in $G$. In (Larson & Pepper 2011) it was conjectured that the following assertions are equivalent: (i) $\alpha\left(G\right) =h\left(G\right) $; (ii) $G$ is a K\"onig-Egerv\'ary graph and every maximum independent set is a maximal annihilating set. In this paper, we prove that the implication "(i) $\Longrightarrow$ (ii)" is correct, while for the opposite direction we provide a series of generic counterexamples. Keywords: maximum independent set, matching, tree, bipartite graph, K\"onig-Egerv\'ary graph, annihilation set, annihilation number., Comment: 17 pages, 11 figures

An independent set A is maximal if it is not a proper subset of an independent set, while A is maximum if it has a maximum size. The problem of whether a graph has a pair of disjoint maximal independent sets was introduced by C. Berge in early 70's. The class of graphs for which every induced subgraph admits two disjoint maximal independent sets was characterized in (Shaudt, 2015). It is known that deciding whether a graph has two disjoint maximal independent sets is a NP-complete problem (Henning et al., 2009). In this paper, we are focused on finding conditions ensuring the existence of two disjoint maximum independent sets., Comment: 12 pages, 4 figures

A graph is well-covered if all its maximal independent sets are of the same cardinality (Plummer, 1970). If G is a well-covered graph, has at least two vertices, and G-v is well-covered for every vertex v, then G is a 1-well-covered graph (Staples, 1975). We call G a {\lambda}-quasi-regularizable graph if {\lambda} |S| =< |N(S)| for every independent set S of G. The independence polynomial I(G;x) is the generating function of independent sets in a graph G (Gutman & Harary, 1983). The Roller-Coaster Conjecture (Michael & Travis, 2003), saying that for every permutation {\sigma} of the set {({\alpha}/2),...,{\alpha}} there exists a well-covered graph G with independence number {\alpha} such that the coefficients (s_{k}) of I(G;x) are chosen in accordance with {\sigma}, has been validated in (Cutler & Pebody, 2017). In this paper, we show that independence polynomials of {\lambda}-quasi-regularizable graphs are partially unimodal. More precisely, the coefficients of an upper part of I(G;x) are in non-increasing order. Based on this finding, we prove that the domain of the Roller- Coaster Conjecture can be shortened for well-covered graphs and 1-well-covered graphs., Comment: 9 pages

A graph is well-covered if all its maximal independent sets are of the same size (M. D. Plummer, 1970). A well-covered graph is 1-well-covered if the deletion of every vertex leaves a graph which is well-covered as well (J. W. Staples, 1975). A graph G belongs to class W_{n} if every n pairwise disjoint independent sets in G are included in $n$ pairwise disjoint maximum independent sets (J. W. Staples, 1975). Clearly, W_{1} is the family of all well-covered graphs. It turns out that G belongs to W_{2} if and only if it is a 1-well-covered graph without isolated vertices. We show that deleting a shedding vertex does not change the maximum size of a maximal independent set including a given independent set A in a graph G. Specifically, for well-covered graphs, it means that the vertex v is shedding if and only if G-v is well-covered. In addition, we provide new characterizations of 1-well-covered graphs, which we further use in building 1-well-covered graphs by corona, join, and concatenation operations., Comment: 19 pages; 4 figures

Let G be a simple graph with vertex set V(G). A set S is independent if no two vertices from S are adjacent. The graph G is known to be a Konig-Egervary if alpha(G)+mu(G)= |V(G)|, where alpha(G) denotes the size of a maximum independent set and mu(G) is the cardinality of a maximum matching. The number d(X)= |X|-|N(X)| is the difference of X, and an independent set A is critical if d(A) = max{d(I):I is an independent set in G} (Zhang; 1990). Let Omega(G) denote the family of all maximum independent sets. Let us say that a family Gamma of independent sets is a Konig-Egervary collection if |Union of Gamma| + |Intersection of Gamma| = 2alpha(G) (Jarden, Levit, Mandrescu; 2015). In this paper, we show that if the family of all maximum critical independent sets of a graph G is a Konig-Egervary collection, then G is a Konig-Egervary graph. It generalizes one of our conjectures recently validated in (Short; 2015)., Comment: 9 pages, 3 figures

Let G be a simple graph with vertex set V(G). A subset S of V(G) is independent if no two vertices from S are adjacent. The graph G is known to be a Konig-Egervary if alpha(G) + mu(G)= |V(G)|, where alpha(G) denotes the size of a maximum independent set and mu(G) is the cardinality of a maximum matching. Let Omega(G) denote the family of all maximum independent sets, and f be the function from the set of subcollections Gamma of Omega(G) such that f(Gamma) = (the cardinality of the union of elements of Gamma) + (the cardinality of the intersection of elements of Gamma). Our main finding claims that f is "<<"-increasing, where the preorder {Gamma1} << {Gamma2} means that the union of all elements of {Gamma1} is a subset of the union of all elements of {Gamma2}, while the intersection of all elements of {Gamma2} is a subset of the intersection of all elements of {Gamma1}. Let us say that a family {Gamma} is a Konig-Egervary collection if f(Gamma) = 2*alpha(G). We conclude with the observation that for every graph G each subcollection of a Konig-Egervary collection is Konig-Egervary as well., Comment: 15 pages, 7 figures

Let G be a simple graph with vertex set V(G). A subset S of V(G) is independent if no two vertices from S are adjacent. By Ind(G) we mean the family of all independent sets of G while core(G) and corona(G) denote the intersection and the union of all maximum independent sets, respectively. The number d(X)= |X|-|N(X)| is the difference of the set of vertices X, and an independent set A is critical if d(A)=max{d(I):I belongs to Ind(G)} (Zhang, 1990). Let ker(G) and diadem(G) be the intersection and union, respectively, of all critical independent sets of G (Levit and Mandrescu, 2012). In this paper, we present various connections between critical unions and intersections of maximum independent sets of a graph. These relations give birth to new characterizations of Koenig-Egervary graphs, some of them involving ker(G), core(G), corona(G), and diadem(G)., Comment: 12 pages, 9 figures. arXiv admin note: substantial text overlap with arXiv:1407.7368

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)$., Comment: 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

An independent set in a graph is a set of pairwise non-adjacent vertices, and a(G) is the size of a maximum independent set in the graph G. If s_{k} is the number of independent sets of cardinality k in G, then I(G;x)=s_0+s_1*x+s_2*x^2+...+s_a*x^a,a=a(G), is called the independence polynomial of G (I. Gutman and F. Harary, 1983). If s_{a-i}=f(i)*s_{i} holds for every i, then I(G;x) is called f-symmetric (f-palindromic). If f(i)=1, then I(G;x) is symmetric (palindromic). The corona of the graphs G and H is the graph G*H obtained by joining each vertex of G to all the vertices of a copy of H. In this paper we show that if H is a graph with p vertices, q edges, and alpha(H)=2, then I(G*H;x) is f-symmetric for some elegant function f. In particular, if H = K_{r}-e, we show that I(G*H;x) is symmetric and unimodal, with a unique mode. This finding generalizes results due to (Stevanovic, 1998) and (Mandrescu, 2012) claiming that I(G*(K_2-e);x)=I(G*2K_1;x) is symmetric and unimodal for every graph G., Comment: 10 pages

A set S is independent in a graph G if no two vertices from S are adjacent. 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)=|V|, then G=(V,E) is called a Konig-Egervary graph. The number d_{c}(G)=max{|A|-|N(A)|} is called the critical difference of G (Zhang, 1990). By core(G) (corona(G)) we denote the intersection (union, respectively) of all maximum independent sets, while by ker(G) we mean the intersection of all critical independent sets. A connected graph having only one cycle is called unicyclic. It is known that ker(G) is a subset of core(G) for every graph G, while the equality is true for bipartite graphs (Levit and Mandrescu, 2011). For Konig-Egervary unicyclic graphs, the difference |core(G)|-|ker(G)| may equal any non-negative integer. In this paper we prove that if G is a non-Konig-Egervary unicyclic graph, then: (i) ker(G)= core(G) and (ii) |corona(G)|+|core(G)|=2*alpha(G)+1. Pay attention that |corona(G)|+|core(G)|=2*alpha(G) holds for every Konig-Egervary graph., Comment: 8 pages, 5 figures

An independent set in a graph is a set of pairwise non-adjacent vertices, and alpha(G) is the size of a maximum independent set in the graph G. A matching is a set of non-incident edges, while mu(G) is the cardinality of a maximum matching. If s_{k} is the number of independent sets of cardinality k in G, then I(G;x)=s_{0}+s_{1}x+s_{2}x^{2}+...+s_{\alpha(G)}x^{\alpha(G)} is called the independence polynomial of G (Gutman and Harary, 1983). If $s_{j}=s_{\alpha-j}$, 0=< j =< alpha(G), then I(G;x) is called symmetric (or palindromic). It is known that the graph G*2K_{1} obtained by joining each vertex of G to two new vertices, has a symmetric independence polynomial (Stevanovic, 1998). In this paper we show that for every graph G and for each non-negative integer k =< mu(G), one can build a graph H, such that: G is a subgraph of H, I(H;x) is symmetric, and I(G*2K_{1};x)=(1+x)^{k}*I(H;x)., Comment: 16 pages, 13 figures

A set S is independent in a graph G if no two vertices from S are adjacent. By core(G) we mean the intersection of all maximum independent sets. 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. 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 = alpha(G) + mu(G), then core(G) coincides with the union of cores of all trees in G-C., Comment: 8 pages, 5 figures

Let G=(V,E). A set S is independent if no two vertices from S are adjacent. The number d(X)= |X|-|N(X)| is the difference of X, and an independent set A is critical if d(A) = max{d(I):I is an independent set}. Let us recall that ker(G) is the intersection of all critical independent sets, and core(G) is the intersection of all maximum independent sets. Recently, it was established that ker(G) is a subset of core(G) is true for every graph, while the corresponding equality holds for bipartite graphs. In this paper we present various structural properties of ker(G). The main finding claims that ker(G) is equal to the union of all inclusion minimal independent sets with positive difference., Comment: 8 pages, 3 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., Comment: 8 pages, 5 figures

A maximum stable set in a graph G is a stable set of maximum cardinality. S is called a local maximum stable set of G if S is a maximum stable set of the subgraph induced by the closed neighborhood of S. A greedoid (V,F) is called a local maximum stable set greedoid if there exists a graph G=(V,E) such that its family of local maximum stable sets coinsides with (V,F). It has been shown that the family local maximum stable sets of a forest T forms a greedoid on its vertex set. In this paper we demonstrate that if G is a very well-covered graph, then its family of local maximum stable sets is a greedoid if and only if G has a unique perfect matching., Comment: 12 pages, 12 figures

Let G=(V,E) be a graph. A set S is independent if no two vertices from S are adjacent, alpha(G) is the size of a maximum independent set, and core(G) is the intersection of all maximum independent sets. The number d(X)=|X|-|N(X)| is the difference of the set X, and d_{c}(G)=max{d(I):I is an independent set} is called the critical difference of G. A set X is critical if d(X)=d_{c}(G). For a graph G we define ker(G) as the intersection of all critical independent sets, while diadem(G) is the union of all critical independent sets. For a bipartite graph G=(A,B,E), with bipartition {A,B}, Ore defined delta(X)=d(X) for every subset X of A, while delta_0(A)=max{delta(X):X is a subset of A}. Similarly is defined delta_0(B). In this paper we prove that for every bipartite graph G=(A,B,E) the following assertions hold: d_{c}(G)=delta_0(A)+delta_0(B); ker(G)=core(G); |ker(G)|+|diadem(G)|=2*alpha(G)., Comment: 13 pages, 8 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., Comment: 9 pages; 4 figures

A set S is independent if no two vertices from S are adjacent. In this paper we prove that if F is a collection of maximum independent sets of a graph, then there is a matching from S-{intersection of all members of F} into {union of all members of F}-S, for every independent set S. Based on this finding we give alternative proofs for a number of well-known lemmata, as the "Maximum Stable Set Lemma" due to Claude Berge and the "Clique Collection Lemma" due to Andr\'as Hajnal., Comment: 7 pages, 3 figures

A \textit{maximum stable set} in a graph $G$ is a stable set of maximum cardinality. $S$ is a \textit{local maximum stable set} of $G$, and we write $S\in\Psi(G)$, if $S$ is a maximum stable set of the subgraph induced by $S\cup N(S)$, where $N(S)$ is the neighborhood of $S$. Nemhauser and Trotter Jr. (1975), proved that any $S\in\Psi(G)$ is a subset of a maximum stable set of $G$. In (Levit & Mandrescu, 2002) we have shown that the family $\Psi(T)$ of a forest $T$ forms a greedoid on its vertex set. The cases where $G$ is bipartite, triangle-free, well-covered, while $\Psi(G)$ is a greedoid, were analyzed in (Levit & Mandrescu, 2002),(Levit & Mandrescu, 2004),(Levit & Mandrescu, 2007), respectively. In this paper we demonstrate that if $G$ is a very well-covered graph of girth $\geq4$, then the family $\Psi(G)$ is a greedoid if and only if $G$ has a unique perfect matching., Comment: 7 pages, 5 figures

A graph with at most two vertices of the same degree is called antiregular (Merris 2003), maximally nonregular (Zykov 1990) or quasiperfect (Behzad, Chartrand 1967). If s_{k} is the number of independent sets of cardinality k in a graph G, then I(G;x) = s_{0} + s_{1}x + ... + s_{alpha}x^{alpha} is the independence polynomial of G (Gutman, Harary 1983), where alpha = alpha(G) is the size of a maximum independent set. In this paper we derive closed formulae for the independence polynomials of antiregular graphs. In particular, we deduce that every antiregular graph A is uniquely defined by its independence polynomial I(A;x), within the family of threshold graphs. Moreover, I(A;x) is logconcave with at most two real roots, and I(A;-1) belongs to {-1,0}., Comment: 11 pages, 5 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., Comment: 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., Comment: 9 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

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., Comment: 8 pages, 5 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 provide an elementary proof of the inequality claiming that the absolute value of I(G;-1) is not greater than 2^phi(G), for every graph G, where phi(G) is its decycling number., Comment: 4 pages

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., Comment: 16 pages; 13 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

S is a local maximum stable set of a graph G, if the set S is a maximum stable set of the subgraph induced by its closed neighborhood. In (Levit, Mandrescu, 2002) we have proved that the family of all local maximum stable sets is a greedoid for every forest. The cases of bipartite graphs and triangle-free graphs were analyzed in (Levit, Mandrescu, 2004) and (Levit, Mandrescu, 2007), respectively. In this paper we give necessary and sufficient conditions for the family of all local maximum stable sets of a graph G to form a greedoid, where G is: (a) the disjoint union of a family of graphs; (b) the Zykov sum of a family of graphs, or (c) the corona X*{H_1,H_2,...,H_n} obtained by joining each vertex k of a graph X to all the vertices of a graph H_k., Comment: 8 pages, 4 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., Comment: 7 pages; 7 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)., Comment: 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<10, and is log-concave whenever a<6., Comment: 10 pages, 4 figures

A graph $G$ is well-covered if all its maximal stable sets have the same size, denoted by alpha(G) (M. D. Plummer, 1970). 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 I(G;x) 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) for any well-covered graph $G$. T. S. Michael and W. N. Traves (2002) proved that this assertion is true for alpha(G) < 4, while for alpha(G) from the set {4,5,6,7} they provided counterexamples. In this paper we show that for any integer $alpha$ > 7, there exists a (dis)connected well-covered graph $G$ with $alpha$ = alpha(G), whose independence polynomial is not unimodal. In addition, we present a number of sufficient conditions for a graph $G$ with alpha(G) < 7 to have unimodal independence polynomial., Comment: 10 pages, 2 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

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). A graph G is very well-covered (Favaron, 1982) if it has no isolated vertices, its order equals 2*alpha(G), where alpha(G) is the size of a maximum stable set, and it is well-covered (i.e., all its maximal independent sets are of the same size, Plummer, 1970). For instance, appending a single pendant edge to each vertex of G yields a very well-covered graph, which we denote by G*. Under certain conditions, any well-covered graph equals G* for some G (Finbow, Hartnell and Nowakowski, 1993). The root of the smallest modulus of the independence polynomial of any graph is real (Brown, Dilcher, and Nowakowski, 2000). The location of the roots of the independence polynomial in the complex plane, and the multiplicity of the root of the smallest modulus are investigated in a number of articles. In this paper we establish formulae connecting the coefficients of I(G;x) and I(G*;x), which allow us to show that the number of roots of I(G;x) is equal to the number of roots of I(G*;x) different from -1, which appears as a root of multiplicity alpha(G*)- alpha(G) for I(G*;x). We also prove that the real roots of I(G*;x) are in [-1,-1/(2*alpha(G*)), while for a general graph of order n we show that its roots lie in |z| > 1/(2n-1). Using the properties of the roots of the independence polynomial, we demonstrate that the independence polynomial distinguishes well-covered spiders (well-covered trees with at most one vertex of degree greater than two) among general well-covered trees., Comment: 17 pages; 6 figures