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

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

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

In many developing countries, the total electricity demand is larger than the limited generation capacity of power stations. Many countries adopt the common practice of routine load shedding - disconnecting entire regions from the power supply - to maintain a balance between demand and supply. Load shedding results in inflicting hardship and discomfort on households, which is even worse and hence unfair to those whose need for electricity is higher than that of others during load shedding hours. Recently, Oluwasuji et al. [2020] presented this problem and suggested several heuristic solutions. In this work, we study the electricity distribution problem as a problem of fair division, model it using the related literature on cake-cutting problems, and discuss some insights on which parts of the time intervals are allocated to each household. We consider four cases: identical demand, uniform utilities; identical demand, additive utilities; different demand, uniform utilities; different demand, additive utilities. We provide the solution for the first two cases and discuss the novel concept of q-times bin packing in relation to the remaining cases. We also show how the fourth case is related to the consensus k-division problem. One can study objectives and constraints using utilitarian and egalitarian social welfare metrics, as well as trying to keep the number of cuts as small as possible. A secondary objective can be to minimize the maximum utility-difference between agents., Comment: 16 pages, 1 figure

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

Let G be a finite group. Let pi be a permutation from S{n}. We study the distribution of probabilities of equality a{1} a{2} ...a{n-1}a{n}=a{pi{1}}^{epsilon{1}} a{pi_{2}}^{epsilon{2}}...a{pi{n-1}}^{epsilon_{n-1}} a_{pi_{n}}^{epsilon{n}}, when pi varies over all the permutations in S{n}, and epsilon{i} varies over the set {+1, -1}. By the paper "Hultman Numbers and Generalized Commuting Probability in Finite Groups" (2017), The case where all epsilon{i} are +1 led to a close connection to Hultman numbers. In this paper we generalize the results, permitting epsilon{i} to be -1. We describe the spectrum of the probabilities of signed permutation equalities in a finite group G. This spectrum turns out to be closely related to the partition of 2^{n}*n! into a sum of the corresponding signed Hultman numbers.

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

A group valued function on a graph is called balanced if the product of its values along any cycle is equal to the identity element of the group. We compute the number of balanced functions from edges and vertices of a directed graph to a finite group., Comment: arXiv admin note: substantial text overlap with arXiv:1303.5456

Let $G$ be a finite group and $\pi$ be a permutation from $S_{n}$. We investigate the distribution of the probabilities of the equality \[ a_{1}a_{2}\cdots a_{n-1}a_{n}=a_{\pi_{1}}a_{\pi_{2}}\cdots a_{\pi_{n-1}}a_{\pi_{n}} \] when $\pi$ varies over all the permutations in $S_{n}$. The probability \[ Pr_{\pi}(G)=Pr(a_{1}a_{2}\cdots a_{n-1}a_{n}=a_{\pi_{1}}a_{\pi_{2}}\cdots a_{\pi_{n-1}}a_{\pi_{n}}) \] is identical to $Pr_{1}^{\omega}(G)$, with \[ \omega=a_{1}a_{2}...a_{n-1}a_{n}a_{\pi_{1}}^{-1}a_{\pi_{2}}^{-1}\cdots a_{\pi_{n-1}}^{-1}a_{\pi_{n}}^{-1}, \] as it is defined in \cite{DasNath1} and \cite{NathDash1}. The notion of commutativity degree, or the probability of a permutation equality $a_{1}a_{2}=a_{2}a_{1}$, for which $n=2$ and $\pi=\langle2\;\;1\rangle$, was introduced and assessed by P. Erd\"{o}s and P. Turan in \cite{ET} in 1968 and by W. H. Gustafson in \cite{G} in 1973. In \cite{G} Gustafson establishes a relation between the probability of $a_{1},a_{2}\in G$ commuting and the number of conjugacy classes in $G$. In this work we define several other parameters, which depend only on a certain interplay between the conjugacy classes of $G$, and compute the probabilities of general permutation equalities in terms of these parameters. It turns out that this probability, for a permutation $\pi$, depends only on the number $c(Gr(\pi))$ of the alternating cycles in the cycle graph $Gr(\pi)$ of $\pi$. The cycle graph of a permutation was introduced by V. Bafna and P. A. Pevzner in \cite{BP}. We describe the spectrum of the probabilities of permutation equalities in a finite group as $\pi$ varies over all the elements of $S_{n}$. This spectrum turns-out to be closely related to the partition of $n!$ into a sum of the corresponding Hultman numbers., Comment: 36 pages

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

The paper investigates relationship between algebraic expressions and graphs. We consider a digraph called a Fibonacci graph which gives a generic example of non-series-parallel graphs. Our intention in this paper is to simplify the expressions of Fibonacci graphs and eventually find their shortest representations. With that end in view, we describe the optimal decomposition method for generating Fibonacci graph expressions that is conjectured to provide these representations. Proof (or disproof) of this conjecture is presented as an open problem., Comment: 11 pages

The paper investigates relationship between algebraic expressions and graphs. We consider a digraph called a Fibonacci graph which gives a generic example of non-series-parallel graphs. Our intention in this paper is to simplify the expressions of Fibonacci graphs and eventually find their shortest representations. With that end in view, we describe the number of methods for generating Fibonacci graph expressions and carry out their comparative analysis., Comment: 39 pages