 |
Discrete Mathematics & Theoretical Computer Science |
vol. 26:3
1. A Note on Graph Burning of Path Forests
Graph burning is a natural discrete graph algorithm inspired by the spread of social contagion. Despite its simplicity, some open problems remain steadfastly unsolved, notably the burning number conjecture, which says that every connected graph of order $m^2$ has burning number at most $m$. Earlier, we showed that the conjecture also holds for a path forest, which is disconnected, provided each of its paths is sufficiently long. However, finding the least sufficient length for this to hold turns out to be nontrivial. In this note, we present our initial findings and conjectures that associate the problem to some naturally impossibly burnable path forests. It is noteworthy that our problem can be reformulated as a topic concerning sumset partition of integers.
Section:
Discrete Algorithms
2. On Generalizations of Pairwise Compatibility Graphs
A graph $G$ is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree and an interval $I$, such that each leaf of the tree is a vertex of the graph, and there is an edge $\{ x, y \}$ in $G$ if and only if the weight of the path in the tree connecting $x$ and $y$ lies within the interval $I$. Originating in phylogenetics, PCGs are closely connected to important graph classes like leaf-powers and multi-threshold graphs, widely applied in bioinformatics, especially in understanding evolutionary processes. In this paper we introduce two natural generalizations of the PCG class, namely $k$-OR-PCG and $k$-AND-PCG, which are the classes of graphs that can be expressed as union and intersection, respectively, of $k$ PCGs. These classes can be also described using the concepts of the covering number and the intersection dimension of a graph in relation to the PCG class. We investigate how the classes of OR-PCG and AND-PCG are related to PCGs, $k$-interval-PCGs and other graph classes known in the literature. In particular, we provide upper bounds on the minimum $k$ for which an arbitrary graph $G$ belongs to $k$-interval-PCGs, $k$-OR-PCG or $k$-AND-PCG classes. For particular graph classes we improve these general bounds. Moreover, we show that, for every integer $k$, there exists a bipartite graph that is not in the $k$-interval-PCGs class, proving that there is no finite $k$ for which the $k$-interval-PCG class contains all the graphs. This answers an open […]
Section:
Graph Theory
3. $2$-polarity and algorithmic aspects of polarity variants on cograph superclasses
A graph $G$ is said to be an $(s, k)$-polar graph if its vertex set admits a partition $(A, B)$ such that $A$ and $B$ induce, respectively, a complete $s$-partite graph and the disjoint union of at most $k$ complete graphs. Polar graphs and monopolar graphs are defined as $(\infty, \infty)$- and $(1, \infty)$-polar graphs, respectively, and unipolar graphs are those graphs with a polar partition $(A, B)$ such that $A$ is a clique. The problems of deciding whether an arbitrary graph is a polar graph or a monopolar graph are known to be NP-complete. In contrast, deciding whether a graph is a unipolar graph can be done in polynomial time. In this work we prove that the three previous problems can be solved in linear time on the classes of $P_4$-sparse and $P_4$-extendible graphs, generalizing analogous results previously known for cographs. Additionally, we provide finite forbidden subgraph characterizations for $(2,2)$-polar graphs on $P_4$-sparse and $P_4$-extendible graphs, also generalizing analogous results recently obtained for the class of cographs.
Section:
Graph Theory