1. The independence polynomial of trees is not always log-concave starting from order 26Ohr Kadrawi, Vadim Levit, 2025, original scientific article Abstract: 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 α(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) = Σ_{k = 0}^α(G) s_k x^k = s₀ + s₁x + s₂x² + ... + s_α(G)x^α(G), where sk represents the number of independent sets in G of size k.
The problem raised by Alavi, Malde, Schwenk, and Erdös in 1987 stated that the independence polynomials of trees are unimodal, and many researchers believed that this problem could be strengthened up to its corresponding log-concave version. However, in 2023, this conjecture was shown to be false by Kadrawi, Levit, Yosef, and Mizrachi. In this paper, we provide further evidence against this conjecture by presenting infinite families of trees with independence polynomials that are not log-concave.
Keywords: tree, independent set, independence polynomial, unimodality, log-concavity
Published in RUP: 22.10.2025; Views: 260; Downloads: 1
 Full text (352,77 KB) |
2. On balanceable and simply balanceable regular graphsMilad Ahanjideh, Martin Milanič, Mary Agnes Milanič, 2025, original scientific article Abstract: We continue the study of balanceable graphs, defined by Caro, Hansberg, and Montejano in 2021 as graphs G such that any 2-coloring of the edges of a sufficiently large complete graph containing sufficiently many edges of each color contains a balanced copy of G (that is, a copy with half the edges of each color). While the problem of recognizing balanceable graphs was conjectured to be NP-complete by Dailly, Hansberg, and Ventura in 2021, balanceable graphs admit an elegant combinatorial characterization: a graph is balanceable if and only there exist two vertex subsets, one containing half of all the graph’s edges and another one such that the corresponding cut contains half of all the graph’s edges. We consider a special case of this property, namely when one of the two sets is a vertex cover, and call the corresponding graphs simply balanceable. We prove a number of results on balanceable and simply balanceable regular graphs. First, we characterize simply balanceable regular graphs via a condition involving the independence number of the graph. Second, we address a question of Dailly, Hansberg, and Ventura from 2021 and show that every cubic graph is balanceable. Third, using Brooks’ theorem, we show that every 4-regular graph with order divisible by 4 is balanceable. Finally, we show that it is NP-complete to determine if a 9-regular graph is simply balanceable.
Keywords: balanceable graph, simply balanceable graph, cubic graph, 4-regular graph, regular graph, independent set
Published in RUP: 06.08.2025; Views: 526; Downloads: 7
Full text (530,38 KB)
This document has more files! More... |
3. Splittable and unsplittable graphs and configurationsNino Bašić, Jan Grošelj, Branko Grünbaum, Tomaž Pisanski, 2019, original scientific article Abstract: We prove that there exist infinitely many splittable and also infinitely many unsplittable cyclic ▫$(n_3)$▫ configurations. We also present a complete study of trivalent cyclic Haar graphs on at most 60 vertices with respect to splittability. Finally, we show that all cyclic flag-transitive configurations with the exception of the Fano plane and the Möbius-Kantor configuration are splittable.
Keywords: configuration of points and lines, unsplittable configuration, unsplittable graph, independent set, Levi graph, Grünbaum graph, splitting type, cyclic Haar graph
Published in RUP: 03.01.2022; Views: 2314; Downloads: 22
Full text (355,79 KB) |
4. On girth and the parameterized complexity of token sliding and token jumpingValentin Bartier, Nicolas Bousquet, Clément Jean Dallard, Kyle Lomer, Amer E. Mouawad, 2021, original scientific article Keywords: combinatorial reconfiguration, independent set, token jumping, token sliding, parameterized complexity
Published in RUP: 16.07.2021; Views: 2357; Downloads: 31
 Link to full text |
5. On girth and the parameterized complexity of token sliding and token jumpingValentin Bartier, Nicolas Bousquet, Clément Jean Dallard, Kyle Lomer, Amer E. Mouawad, 2020, published scientific conference contribution Keywords: combinatorial reconfiguration, independent set, token jumping, token sliding, parameterized complexity
Published in RUP: 17.12.2020; Views: 2535; Downloads: 35
Link to full text |
6. Mind the independence gapTinaz Ekim, Didem Gozüpek, Ademir Hujdurović, Martin Milanič, 2020, original scientific article Keywords: maximal independent set, independent dominating set, well-covered graph, hereditary independence gap, polynomial-time algorithm, NP-hard problem
Published in RUP: 19.05.2020; Views: 4006; Downloads: 63
Link to full text |
7. |
8. |
9. |
10. |
