On the Maximal Independence Polynomial of the Covering Graph of the Hypercube up to n=6

D. I. Ignatov

doi:10.1007/978-3-031-35949-1_11

Publications

?

On the Maximal Independence Polynomial of the Covering Graph of the Hypercube up to n=6

P. 152–165.

Ignatov D. I.

There are well-known problems in extremal set theory that can be formulated as enumeration of the maximal independent sets or counting their total number in certain graphs. Here we provide an FCA-based solution on the number of maximal independent sets of the covering graph of a hypercube. In addition, we consider the related maximal independence polynomials for n up to 6, and prove several properties of the polynomials’ coefficients and the corresponding concept lattices.

Language: English

DOI

Text on another site

Keywords: maximal independent set Close-by-one hypercube maximal independence polynomial

Publication based on the results of:

Models and method for analysis of unstructured data, data mining and recommender systems (2023)

In book

17th International Conference, ICFCA 2023, Kassel, Germany, July 17–21, 2023, Proceedings. Formal Concept Analysis, (LNCS, volume 13934)

Switzerland: Springer, 2023.

On the minimum number of maximal distance-k independent sets in trees

Taletskii D., / Series arXiv "math". 2026.

A vertex subset of a graph is called a \textit{distance-$k$ independent set} if the distance between any two of its distinct vertices is at least $k + 1$. For all $n,k \geq 1$, we determine the minimum possible number of inclusion-wise maximal distance-$k$ independent sets among all $n$-vertex trees. It equals~$n$ if $n \leq k ...

Added: May 1, 2026

Solving strongly convex-concave composite saddle-point problems with low dimension of one group of variable

Alkousa M., Gasnikov A., Gladin E. et al., Sbornik Mathematics 2023 Vol. 214 No. 3 P. 285–333

ncave saddle-point problems in the case when one group of variables has a high dimension, while another has a rather low dimension (up to 100). These methods are based on reducing problems of this type to the minimization (maximization) problem for a convex (concave) functional with respect to one of the variables such that an approximate value of the ...

Added: November 6, 2024

The number of maximal independent sets in trees with a given number of leaves

Taletskii D., Malyshev D., Discrete Applied Mathematics 2022 Vol. 314 P. 321–330

For any n and l, we completely describe trees with the maximum and minimum numbers of maximal independent sets among all n-vertex trees with l leaves. ...

Added: March 30, 2022

Trees with a given number of leaves and the maximal number of maximum independent sets

Taletskii D., Malyshev D., Discrete Mathematics and Applications 2021 Vol. 31 No. 2 P. 135–144

A complete description of trees with maximal possible number of maximum independent setsamong all 𝑛-vertex trees with exactly 𝑙 leaves is obtained. For all values of the parameters 𝑛 and 𝑙, the extremal tree is unique and is the result of merging the endpoints of 𝑙 simple paths. ...

Added: April 13, 2021

Trees without twin-leaves with smallest number of maximal independent sets

Taletskii D., Malyshev D., Discrete Mathematics and Applications 2020 Vol. 30 No. 1 P. 53–67

For any n, in the set of n-vertex trees such that any two leaves have no common adjacent vertex, we describe the trees with the smallest number of maximal independent sets. ...

Added: February 12, 2020

On the number of maximal independent sets in complete q-ary trees

Taletskii D., Malyshev D., Discrete Mathematics and Applications 2017 Vol. 27 No. 5 P. 311–318

We investigate the number of maximal independent sets in q-ary trees of height n, when q is fixed and n tends to infinity. ...

Added: October 14, 2017