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

A graph $G$ is well-covered if all maximal independent sets are of the same cardinality. Let $w:V(G) \longrightarrow\mathbb{R}$ be a weight function. Then $G$ is $w$-well-covered if all maximal independent sets are of the same weight. An edge $xy \in E(G)$ is relating if there exists an independent set $S$ such that both $S \cup \{x\}$ and $S \cup \{y\}$ are maximal independent sets in the graph. If $xy$ is relating then $w(x)=w(y)$ for every weight function $w$ such that $G$ is $w$-well-covered. Relating edges play an important role in investigating $w$-well-covered graphs. The decision problem whether an edge in a graph is relating is NP-complete. We prove that the problem remains NP-complete when the input is restricted to graphs without cycles of length $6$. This is an unexpected result because recognizing relating edges is known to be polynomially solvable for graphs without cycles of lengths $4$ and $6$, graphs without cycles of lengths $5$ and $6$, and graphs without cycles of lengths $6$ and $7$. A graph $G$ belongs to the class $W_2$ if every two pairwise disjoint independent sets in $G$ are included in two pairwise disjoint maximum independent sets. It is known that if $G$ belongs to the class $W_2$, then it is well-covered. A vertex $v \in V(G)$ is shedding if for every independent set $S \subseteq V(G)-N[v]$, there exists a vertex $u \in N(v)$ such that $S \cup \{u\}$ is independent. Shedding vertices play an important role in studying the class $W_2$. Recognizing shedding vertices is co-NP-complete, even when the input is restricted to triangle-free graphs. We prove that the problem is co-NP-complete for graphs without cycles of length $6$., Comment: 10 pages. arXiv admin note: text overlap with arXiv:1808.10137

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

Given a graph $G$, the number of its vertices is represented by $n(G)$, while the number of its edges is denoted as $m(G)$. An independent set in a graph is a set of vertices where no two vertices are adjacent to each other and the size of the maximum independent set is denoted by $\alpha(G)$. A matching in a graph refers to a set of edges where no two edges share a common vertex and the maximum matching size is denoted by $\mu(G)$. If $\alpha(G) + \mu(G) = n(G)$, then the graph $G$ is called a K\"{o}nig-Egerv\'{a}ry graph. Considering a graph $G$ with a degree sequence $d_1 \leq d_2 \leq \cdots \leq d_n$, the annihilation number $a(G)$ is defined as the largest integer $k$ such that the sum of the first $k$ degrees in the sequence is less than or equal to $m(G)$ (Pepper, 2004). It is a known fact that $\alpha(G)$ is less than or equal to $a(G)$ for any graph $G$. Our goal is to estimate the difference between these two parameters. Specifically, we prove a series of inequalities, including $a(G) - \alpha(G) \leq \frac{\mu(G) - 1}{2}$ for trees, $a(G) - \alpha(G) \leq 2 + \mu(G) - 2\sqrt{1 + \mu(G)}$ for bipartite graphs and $a(G) - \alpha(G) \leq \mu(G) - 2$ for K\"{o}nig-Egerv\'{a}ry graphs. Furthermore, we demonstrate that these inequalities serve as tight upper bounds for the difference between the annihilation and independence numbers, regardless of the assigned value for $\mu(G)$., Comment: 17 pages, 10 figures

Let $G$ be a graph. A set $S \subseteq V(G)$ is independent if its elements are pairwise non-adjacent. A vertex $v \in V(G)$ is shedding if for every independent set $S \subseteq V(G) \setminus N[v]$ there exists $u \in N(v)$ such that $S \cup \{u\}$ is independent. An independent set $S$ is maximal if it is not contained in another independent set. An independent set $S$ is maximum if the size of every independent set of $G$ is not bigger than $|S|$. The size of a maximum independent set of $G$ is denoted $\alpha(G)$. A graph $G$ is well-covered if all its maximal independent sets are maximum, i.e. the size of every maximal independent set is $\alpha(G)$. The graph $G$ belongs to class $\mathbf{W_2}$ if every two pairwise disjoint independent sets in $G$ are included in two pairwise disjoint maximum independent sets. If a graph belongs to the class $\mathbf{W_2}$ then it is well-covered. Finding a maximum independent set in an input graph is an NP-complete problem. Recognizing well-covered graphs is co-NP-complete. The complexity status of deciding whether an input graph belongs to the $\mathbf{W_2}$ class is not known. Even when the input is restricted to well-covered graphs, the complexity status of recognizing graphs in $\mathbf{W_2}$ is not known. In this article, we investigate the connection between shedding vertices and $\mathbf{W_2}$ graphs. On the one hand, we prove that recognizing shedding vertices is co-NP-complete. On the other hand, we find polynomial solutions for restricted cases of the problem. We also supply polynomial characterizations of several families of $\mathbf{W_2}$ graphs., Comment: 15 pages, 2 figures, 1 table

An independent set in a graph is a collection of vertices that are not adjacent to each other. The cardinality of the largest independent set in $G$ is represented by $\alpha(G)$. The independence polynomial of a graph $G = (V, E)$ was introduced by Gutman and Harary in 1983 and is defined as \[ I(G;x) = \sum_{k=0}^{\alpha(G)}{s_k}x^{k}={s_0}+{s_1}x+{s_2}x^{2}+...+{s_{\alpha(G)}}x^{\alpha(G)}, \] where $s_k$ represents the number of independent sets in $G$ of size $k$. The conjecture made by Alavi, Malde, Schwenk, and Erd\"os in 1987 stated that the independence polynomials of trees are unimodal, and many researchers believed that this conjecture could be strengthened up to its corresponding log-concave version. However, in our paper, we present evidence that contradicts this assumption by introducing infinite families of trees whose independence polynomials are not log-concave., Comment: 25 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

An independent set in a graph is a set of pairwise non-adjacent vertices. Let $\alpha(G)$ denote the cardinality of a maximum independent set in the graph $G = (V, E)$. Gutman and Harary defined the independence polynomial of $G$ \[ I(G;x) = \sum_{k=0}^{\alpha(G)}{s_k}x^{k}={s_0}+{s_1}x+{s_2}x^{2}+...+{s_{\alpha(G)}}x^{\alpha(G)}, \] where $s_k$ denotes the number of independent sets of cardinality $k$ in the graph $G$. A comprehensive survey on the subject is due to Levit and Mandrescu, where some recursive formulas are allowing to calculate the independence polynomial. A direct implementation of these recursions does not bring about an efficient algorithm. Yosef, Mizrachi, and Kadrawi developed an efficient way for computing the independence polynomials of trees with $n$ vertices, such that a database containing all of the independence polynomials of all the trees with up to $n-1$ vertices is required. This approach is not suitable for big trees, as an extensive database is needed. On the other hand, using dynamic programming, it is possible to develop an efficient algorithm that prevents repeated calculations. In summary, our dynamic programming algorithm runs over a tree in linear time and does not depend on a database., Comment: 8 pages

Given a finite set $E$ and an operator $\sigma:2^{E}\longrightarrow2^{E}$, two sets $X,Y\subseteq E$ are \textit{cospanning} if $\sigma\left( X\right) =\sigma\left( Y\right) $. Corresponding \textit{cospanning equivalence relations} were investigated for greedoids in much detail (Korte, Lovasz, Schrader; 1991). For instance, these relations determine greedoids uniquely. In fact, the feasible sets of a greedoid are exactly the inclusion-wise minimal sets of the equivalence classes. In this research, we show that feasible sets of convex geometries are the inclusion-wise maximal sets of the equivalence classes of the corresponding closure operator. Same as greedoids, convex geometries are uniquely defined by the corresponding cospanning relations. For each closure operator $\sigma$, an element $x\in X$ is \textit{an extreme point} of $X$ if $x\notin\sigma(X-x)$. The set of extreme points of $X$ is denoted by $ex(X)$. We prove, that if $\sigma$ has the anti-exchange property, then for every set $X$ its equivalence class $[X]_{\sigma}$ is the interval $[ex(X),\sigma(X)]$. It results in the one-to-one correspondence between the cospanning partitions of an antimatroid and its complementary convex geometry. The obtained results are based on the connection between violator spaces, greedoids, and antimatroids. Cospanning characterization of these combinatorial structures allows us not only to give the new characterization of antimatroids and convex geometries but also to obtain the new properties of closure operators, extreme point operators, and their interconnections., Comment: 20 pages. arXiv admin note: text overlap with arXiv:2105.05074

Given a finite set E and an operator sigma:2^{E}-->2^{E}, two subsets X,Y of the ground set E are cospanning if sigma(X)=sigma(Y) (Korte, Lovasz, Schrader; 1991). We investigate cospanning relations on violator spaces. A notion of a violator space was introduced in (Gartner, Matousek, Rust, Skovrovn; 2008) as a combinatorial framework that encompasses linear programming and other geometric optimization problems. Violator spaces are defined by violator operators. We introduce co-violator spaces based on contracting operators known also as choice functions. Let alpha,beta:2^{E}-->2^{E} be a violator operator and a co-violator operator, respectively. Cospanning characterizations of violator spaces allow us to obtain some new properties of violator operators, co-violator operators, and their interconnections. In particular, we show that uniquely generated violator spaces enjoy so-called Krein-Milman properties, i.e., alpha(beta(X))=alpha(X) and beta(alpha}(X))=beta(X) for every subset X of the ground set E., Comment: 10 pages

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

A graph $G$ is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function $w$ is defined on its vertices. Then $G$ is $w$-well-covered if all maximal independent sets are of the same weight. For every graph $G$, the set of weight functions $w$ such that $G$ is $w$-well-covered is a vector space, denoted as $WCW(G).$ Deciding whether an input graph $G$ is well-covered is co-NP-complete. Therefore, finding $WCW(G)$ is co-NP-hard. A generating subgraph of a graph $G$ is an induced complete bipartite subgraph $B$ of $G$ on vertex sets of bipartition $B_{X}$ and $B_{Y}$, such that each of $S \cup B_{X}$ and $S \cup B_{Y}$ is a maximal independent set of $G$, for some independent set $S$. If $B$ is generating, then $w(B_{X})=w(B_{Y})$ for every weight function $w \in WCW(G)$. Therefore, generating subgraphs play an important role in finding $WCW(G)$. The decision problem whether a subgraph of an input graph is generating is known to be NP-complete. In this article, we prove NP-completeness of the problem for graphs without cycles of length 3 and 5, and for bipartite graphs with girth at least 6. On the other and, we supply polynomial algorithms for recognizing generating subgraphs and finding $WCW(G)$, when the input graph is bipartite without cycles of length 6. We also present a polynomial algorithm which finds $WCW(G)$ when $G$ does not contain cycles of lengths 3, 4, 5, and 7., Comment: 22 pages, 2 figures. arXiv admin note: text overlap with arXiv:1401.0294

A graph $G$ is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function $w$ is defined on its vertices. Then $G$ is $w$-well-covered if all maximal independent sets are of the same weight. For every graph $G$, the set of weight functions $w$ such that $G$ is $w$-well-covered is a vector space, denoted $WCW(G)$. Let $B$ be a complete bipartite induced subgraph of $G$ on vertex sets of bipartition $B_{X}$ and $B_{Y}$. Then $B$ is generating if there exists an independent set $S$ such that $S \cup B_{X}$ and $S \cup B_{Y}$ are both maximal independent sets of $G$. In the restricted case that a generating subgraph $B$ is isomorphic to $K_{1,1}$, the unique edge in $B$ is called a relating edge. Generating subgraphs play an important role in finding $WCW(G)$. Deciding whether an input graph $G$ is well-covered is co-NP-complete. Hence, finding $WCW(G)$ is co-NP-hard. Deciding whether an edge is relating is NP-complete. Therefore, deciding whether a subgraph is generating is NP-complete as well. A graph is chordal if every induced cycle is a triangle. It is known that finding $WCW(G)$ can be done polynomially in the restricted case that $G$ is chordal. Thus recognizing well-covered chordal graphs is a polynomial problem. We present a polynomial algorithm for recognizing relating edges and generating subgraphs in chordal graphs., Comment: 13 pages, 1 figure. arXiv admin note: text overlap with arXiv:1401.0294

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

Violator Spaces were introduced by J. Matousek et al. in 2008 as generalization of Linear Programming problems. Convex geometries were invented by Edelman and Jamison in 1985 as proper combinatorial abstractions of convexity. Convex geometries are defined by anti-exchange closure operators. We investigate an interrelations between violator spaces and closure spaces and show that violator mapping may be defined by a week version of closure operators. Moreover, we prove that violator spaces with an unique basis satisfies the anti-exchange and the Krein-Milman properties.

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 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 minimal 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 $WWD(G)$. We prove that $WWD(G)$ is a subspace of $WCW(G)$, the vector space of weight functions $w$ such that $G$ is $w$-well-covered. We provide a polynomial characterization of $WWD(G)$ for the case that $G$ does not contain cycles of lengths $4$, $5$, and $6$., Comment: 10 pages, 2 figures

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

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space, denoted WCW(G). Let B be a complete bipartite induced subgraph of G on vertex sets of bipartition B_X and B_Y. Then B is generating if there exists an independent set S such that S \cup B_X and S \cup B_Y are both maximal independent sets of G. A relating edge is a generating subgraph in the restricted case that B = K_{1,1}. Deciding whether an input graph G is well-covered is co-NP-complete. Therefore finding WCW(G) is co-NP-hard. Deciding whether an edge is relating is co-NP-complete. Therefore, deciding whether a subgraph is generating is co-NP-complete as well. In this article we discuss the connections among these problems, provide proofs for NP-completeness for several restricted cases, and present polynomial characterizations for some other cases., Comment: 18 pages, 3 figures, 1 table. arXiv admin note: text overlap with arXiv:1312.7563

A graph G is well-covered if all its maximal independent sets are of the same cardinality. Assume that a weight function w is defined on its vertices. Then G is w-well-covered if all maximal independent sets are of the same weight. For every graph G, the set of weight functions w such that G is w-well-covered is a vector space. Given an input claw-free graph G, we present an O(n^6)algortihm, whose input is a claw-free graph G, and output is the vector space of weight functions w, for which G is w-well-covered. A graph G is equimatchable if all its maximal matchings are of the same cardinality. Assume that a weight function w is defined on the edges of G. Then G is w-equimatchable if all its maximal matchings are of the same weight. For every graph G, the set of weight functions w such that G is w-equimatchable is a vector space. We present an O(m*n^4 + n^5*log(n)) algorithm which receives an input graph G, and outputs the vector space of weight functions w such that G is w-equimatchable., Comment: 14 pages, 1 figure

The paper is devoted to the methods of solving simultaneous recurrences. Specifically, we discuss transformation of matrix recurrences to regular recurrences and propose a way of solving special matrix recurrences of order three by their decomposition to matrix recurrences of order two., Comment: 22 pages

We define two recursive functions obtained by decomposition of a given interval into four close parts and prove two lemmas which determine features of these functions., Comment: 18 pages

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

An edge xy is relating in the graph G if there is an independent set S, containing neither x nor y, such that S_{x} and S_{y} are both maximal independent sets in G. It is an NP-complete problem to decide whether an edge is relating (Brown, Nowakowski, Zverovich, 2007). We show that the problem remains NP-complete even for graphs without cycles of length 4 and 5. On the other hand, for graphs without cycles of length 4 and 6, the problem can be solved in polynomial time., Comment: 6 pages, 1 figure

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