Vadim E. Levit
On Symmetry of Independence Polynomials.
Thu, 05/12/2011 - 15:01 — SomNambulAuthors: Vadim E. Levit, Eugen Mandrescu
Subjects: Discrete Mathematics
AbstractAn 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.Weighted Well-Covered Graphs without Cycles of Length 4, 5, 6 and 7.
Fri, 09/17/2010 - 15:02 — SomNambulAuthors: Vadim E. Levit, David Tankus
Subjects: Discrete Mathematics
AbstractA graph is well-covered if every maximal independent set has the same
cardinality. The recognition problem of well-covered graphs is known to be
co-NP-complete. Let w be a weight function defined on the vertices of G. Then G
is w-well-covered if all maximal independent sets of G are of the same weight.
The set of weight functions w for which a graph is w-well-covered is a vector
space. We prove that finding the vector space of weight functions under which
an input graph is w-well-covered can be done in polynomial time, if the input
graph does not contain cycles of length 4, 5, 6 and 7.Very Well-Covered Graphs of Girth at least Four and Local Maximum Stable Set Greedoids.
Wed, 08/18/2010 - 15:02 — SomNambulAuthors: Vadim E. Levit, Eugen Mandrescu
Subjects: Discrete Mathematics
AbstractA \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.On the independence polynomial of an antiregular graph.
Wed, 07/07/2010 - 15:01 — SomNambulAuthors: Vadim E. Levit, Eugen Mandrescu
Subjects: Discrete Mathematics
AbstractA 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.A characterization of Konig-Egervary graphs using a common property of all maximum matchings.
Wed, 11/25/2009 - 16:01 — SomNambulAuthors: Vadim E. Levit, Eugen Mandrescu
Subjects: Discrete Mathematics
AbstractThe 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.
User login
