Graph Theory

---

The Widths of Strict Outerconfluent Graphs

David Eppstein.

Strict outerconfluent drawing is a style of graph drawing in which vertices are drawn on the boundary of a disk, adjacencies are indicated by the existence of smooth curves through a system of tracks within the disk, and no two adjacent vertices are connected by more than one of these smooth tracks. We investigate graph width parameters on the graphs that have drawings in this style. We prove that the clique-width of these graphs is unbounded, but their twin-width is bounded.

---

Uniquely hamiltonian graphs for many sets of degrees

Gunnar Brinkmann ; Matthias De Pauw.

We give constructive proofs for the existence of uniquely hamiltonian graphs for various sets of degrees. We give constructions for all sets with minimum 2 (a trivial case added for completeness), all sets with minimum 3 that contain an even number (for sets without an even number it is known that no uniquely hamiltonian graphs exist), and all sets with minimum 4, except {4}, {4,5}, and {4,6}. For minimum degree 3 and 4, the constructions also give 3-connected graphs. We also introduce the concept of seeds, which makes the above results possible and might be useful in the study of Sheehan's conjecture. Furthermore, we prove that 3-connected uniquely hamiltonian 4-regular graphs exist if and only if 2-connected uniquely hamiltonian 4-regular graphs exist.

---

Spanning trees for many different numbers of leaves

Kenta Noguchi ; Carol T. Zamfirescu.

Let $G$ be a connected graph and $L(G)$ the set of all integers $k$ such that $G$ contains a spanning tree with exactly $k$ leaves. We show that for a connected graph $G$, the set $L(G)$ is contiguous. It follows from work of Chen, Ren, and Shan that every connected and locally connected $n$-vertex graph -- this includes triangulations -- has a spanning tree with at least $n/2 + 1$ leaves, so by a classic theorem of Whitney and our result, in any plane $4$-connected $n$-vertex triangulation one can find for any integer $k$ which is at least $2$ and at most $n/2 + 1$ a spanning tree with exactly $k$ leaves (and each of these trees can be constructed in polynomial time). We also prove that there exist infinitely many $n$ such that there is a plane $4$-connected $n$-vertex triangulation containing a spanning tree with $2n/3$ leaves, but no spanning tree with more than $2n/3$ leaves.

---

On the mod $k$ chromatic index of graphs

Oothan Nweit ; Daqing Yang.

For a graph $G$ and an integer $k\geq 2$, a $\chi'_{k}$-coloring of $G$ is an edge coloring of $G$ such that the subgraph induced by the edges of each color has all degrees congruent to $1 ~ (\mod k)$, and $\chi'_{k}(G)$ is the minimum number of colors in a $\chi'_{k}$-coloring of $G$. In ["The mod $k$ chromatic index of graphs is $O(k)$", J. Graph Theory. 2023; 102: 197-200], Botler, Colucci and Kohayakawa proved that $\chi'_{k}(G)\leq 198k-101$ for every graph $G$. In this paper, we show that $\chi'_{k}(G) \leq 177k-93$.

---

$2$-polarity and algorithmic aspects of polarity variants on cograph superclasses

Fernando Esteban Contreras-Mendoza ; César Hernández-Cruz.

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.

---

On Generalizations of Pairwise Compatibility Graphs

Tiziana Calamoneri ; Manuel Lafond ; Angelo Monti ; Blerina Sinaimeri.

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 […]

---

Line game-perfect graphs

Stephan Dominique Andres ; Wai Lam Fong.

The $[X,Y]$-edge colouring game is played with a set of $k$ colours on a graph $G$ with initially uncoloured edges by two players, Alice (A) and Bob (B). The players move alternately. Player $X\in\{A,B\}$ has the first move. $Y\in\{A,B,-\}$. If $Y\in\{A,B\}$, then only player $Y$ may skip any move, otherwise skipping is not allowed for any player. A move consists of colouring an uncoloured edge with one of the $k$ colours such that adjacent edges have distinct colours. When no more moves are possible, the game ends. If every edge is coloured in the end, Alice wins; otherwise, Bob wins. The $[X,Y]$-game chromatic index $\chi_{[X,Y]}'(G)$ is the smallest nonnegative integer $k$ such that Alice has a winning strategy for the $[X,Y]$-edge colouring game played on $G$ with $k$ colours. The graph $G$ is called line $[X,Y]$-perfect if, for any edge-induced subgraph $H$ of $G$, \[\chi_{[X,Y]}'(H)=\omega(L(H)),\] where $\omega(L(H))$ denotes the clique number of the line graph of $H$. For each of the six possibilities $(X,Y)\in\{A,B\}\times\{A,B,-\}$, we characterise line $[X,Y]$-perfect graphs by forbidden (edge-induced) subgraphs and by explicit structural descriptions, respectively.

---

On harmonious coloring of hypergraphs

Sebastian Czerwiński.

A harmonious coloring of a $k$-uniform hypergraph $H$ is a vertex coloring such that no two vertices in the same edge have the same color, and each $k$-element subset of colors appears on at most one edge. The harmonious number $h(H)$ is the least number of colors needed for such a coloring. The paper contains a new proof of the upper bound $h(H)=O(\sqrt[k]{k!m})$ on the harmonious number of hypergraphs of maximum degree $\Delta$ with $m$ edges. We use the local cut lemma of A. Bernshteyn.

---

Leanness Computation: Small Values and Special Graph Classes

David Coudert ; Samuel Coulomb ; Guillaume Ducoffe.

Let u and v be vertices in a connected graph G = (V, E). For any integer k such that 0 ≤ k ≤ dG (u, v), the k-slice Sk (u, v) contains all vertices x on a shortest uv-path such that dG (u, x) = k. The leanness of G is the maximum diameter of a slice. This metric graph invariant has been studied under different names, such as "interval thinness" and "fellow traveler property". Graphs with leanness equal to 0, a.k.a. geodetic graphs, also have received special attention in Graph Theory. The practical computation of leanness in real-life complex networks has been studied recently (Mohammed et al., COMPLEX NETWORKS'21). In this paper, we give a finer-grained complexity analysis of two related problems, namely: deciding whether the leanness of a graph G is at most some small value ℓ; and computing the leanness on specific graph classes. We obtain improved algorithms in some cases, and time complexity lower bounds under plausible hypotheses.

---

A new sufficient condition for a 2-strong digraph to be Hamiltonian

Samvel Kh. Darbinyan.

In this paper we prove the following new sufficient condition for a digraph to be Hamiltonian: {\it Let $D$ be a 2-strong digraph of order $n\geq 9$. If $n-1$ vertices of $D$ have degrees at least $n+k$ and the remaining vertex has degree at least $n-k-4$, where $k$ is a non-negative integer, then $D$ is Hamiltonian}. This is an extension of Ghouila-Houri's theorem for 2-strong digraphs and is a generalization of an early result of the author (DAN Arm. SSR (91(2):6-8, 1990). The obtained result is best possible in the sense that for $k=0$ there is a digraph of order $n=8$ (respectively, $n=9$) with the minimum degree $n-4=4$ (respectively, with the minimum $n-5=4$) whose $n-1$ vertices have degrees at least $n-1$, but it is not Hamiltonian. We also give a new sufficient condition for a 3-strong digraph to be Hamiltonian-connected.

---

A note on removable edges in near-bricks

Deyu Wu ; Yipei Zhang ; Xiumei Wang.

An edge $e$ of a matching covered graph $G$ is removable if $G-e$ is also matching covered. Carvalho, Lucchesi, and Murty showed that every brick $G$ different from $K_4$ and $\overline{C_6}$ has at least $\Delta-2$ removable edges, where $\Delta$ is the maximum degree of $G$. In this paper, we generalize the result to irreducible near-bricks, where a graph is irreducible if it contains no single ear of length three or more.

---

Extending partial edge colorings of iterated cartesian products of cycles and paths

Carl Johan Casselgren ; Jonas B. Granholm ; Fikre B. Petros.

We consider the problem of extending partial edge colorings of iterated cartesian products of even cycles and paths, focusing on the case when the precolored edges satisfy either an Evans-type condition or is a matching. In particular, we prove that if $G=C^d_{2k}$ is the $d$th power of the cartesian product of the even cycle $C_{2k}$ with itself, and at most $2d-1$ edges of $G$ are precolored, then there is a proper $2d$-edge coloring of $G$ that agrees with the partial coloring. We show that the same conclusion holds, without restrictions on the number of precolored edges, if any two precolored edges are at distance at least $4$ from each other. For odd cycles of length at least $5$, we prove that if $G=C^d_{2k+1}$ is the $d$th power of the cartesian product of the odd cycle $C_{2k+1}$ with itself ($k\geq2$), and at most $2d$ edges of $G$ are precolored, then there is a proper $(2d+1)$-edge coloring of $G$ that agrees with the partial coloring. Our results generalize previous ones on precoloring extension of hypercubes [Journal of Graph Theory 95 (2020) 410--444].

---

Weakly toll convexity and proper interval graphs

Mitre C. Dourado ; Marisa Gutierrez ; Fábio Protti ; Silvia Tondato.

A walk $u_0u_1 \ldots u_{k-1}u_k$ is a \textit{weakly toll walk} if $u_0u_i \in E(G)$ implies $u_i = u_1$ and $u_ju_k\in E(G)$ implies $u_j=u_{k-1}$. A set $S$ of vertices of $G$ is {\it weakly toll convex} if for any two non-adjacent vertices $x,y \in S$ any vertex in a weakly toll walk between $x$ and $y$ is also in $S$. The {\em weakly toll convexity} is the graph convexity space defined over weakly toll convex sets. Many studies are devoted to determine if a graph equipped with a convexity space is a {\em convex geometry}. An \emph{extreme vertex} is an element $x$ of a convex set $S$ such that the set $S\backslash\{x\}$ is also convex. A graph convexity space is said to be a convex geometry if it satisfies the Minkowski-Krein-Milman property, which states that every convex set is the convex hull of its extreme vertices. It is known that chordal, Ptolemaic, weakly polarizable, and interval graphs can be characterized as convex geometries with respect to the monophonic, geodesic, $m^3$, and toll convexities, respectively. Other important classes of graphs can also be characterized in this way. In this paper, we prove that a graph is a convex geometry with respect to the weakly toll convexity if and only if it is a proper interval graph. Furthermore, some well-known graph invariants are studied with respect to the weakly toll convexity.

---

Maker-Breaker domination number for Cartesian products of path graphs $P_2$ and $P_n$

Jovana Forcan ; Jiayue Qi.

We study the Maker-Breaker domination game played by Dominator and Staller on the vertex set of a given graph. Dominator wins when the vertices he has claimed form a dominating set of the graph. Staller wins if she makes it impossible for Dominator to win, or equivalently, she is able to claim some vertex and all its neighbours. Maker-Breaker domination number $\gamma_{MB}(G)$ ($\gamma '_{MB}(G)$) of a graph $G$ is defined to be the minimum number of moves for Dominator to guarantee his winning when he plays first (second). We investigate these two invariants for the Cartesian product of any two graphs. We obtain upper bounds for the Maker-Breaker domination number of the Cartesian product of two arbitrary graphs. Also, we give upper bounds for the Maker-Breaker domination number of the Cartesian product of the complete graph with two vertices and an arbitrary graph. Most importantly, we prove that $\gamma'_{MB}(P_2\square P_n)=n$ for $n\geq 1$, $\gamma_{MB}(P_2\square P_n)$ equals $n$, $n-1$, $n-2$, for $1\leq n\leq 4$, $5\leq n\leq 12$, and $n\geq 13$, respectively. For the disjoint union of $P_2\square P_n$s, we show that $\gamma_{MB}'(\dot\cup_{i=1}^k(P_2\square P_n)_i)=k\cdot n$ ($n\geq 1$), and that $\gamma_{MB}(\dot\cup_{i=1}^k(P_2\square P_n)_i)$ equals $k\cdot n$, $k\cdot n-1$, $k\cdot n-2$ for $1\leq n\leq 4$, $5\leq n\leq 12$, and $n\geq 13$, respectively.

---

Connected greedy colourings of perfect graphs and other classes: the good, the bad and the ugly

Laurent Beaudou ; Caroline Brosse ; Oscar Defrain ; Florent Foucaud ; Aurélie Lagoutte ; Vincent Limouzy ; Lucas Pastor.

The Grundy number of a graph is the maximum number of colours used by the "First-Fit" greedy colouring algorithm over all vertex orderings. Given a vertex ordering $\sigma= v_1,\dots,v_n$, the "First-Fit" greedy colouring algorithm colours the vertices in the order of $\sigma$ by assigning to each vertex the smallest colour unused in its neighbourhood. By restricting this procedure to vertex orderings that are connected, we obtain {\em connected greedy colourings}. For some graphs, all connected greedy colourings use exactly $\chi(G)$ colours; they are called {\em good graphs}. On the opposite, some graphs do not admit any connected greedy colouring using only $\chi(G)$ colours; they are called {\em ugly graphs}. We show that no perfect graph is ugly. We also give simple proofs of this fact for subclasses of perfect graphs (block graphs, comparability graphs), and show that no $K_4$-minor free graph is ugly. Moreover, our proofs are constructive, and imply the existence of polynomial-time algorithms to compute good connected orderings for these graph classes.

---

Corrigendum to "On the monophonic rank of a graph" [Discrete Math. Theor. Comput. Sci. 24:2 (2022) #3]

Mitre C. Dourado ; Vitor S. Ponciano ; Rômulo L. O. da Silva.

In this corrigendum, we give a counterexample to Theorem 5.2 in "On the monophonic rank of a graph" [Discrete Math. Theor. Comput. Sci. 24:2 (2022) #3]. We also present a polynomial-time algorithm for computing the monophonic rank of a starlike graph.

---

The bipartite Ramsey numbers $BR(C_8, C_{2n})$

Mostafa Gholami ; Yaser Rowshan.

For the given bipartite graphs $G_1,G_2,\ldots,G_t$, the multicolor bipartite Ramsey number $BR(G_1,G_2,\ldots,G_t)$ is the smallest positive integer $b$ such that any $t$-edge-coloring of $K_{b,b}$ contains a monochromatic subgraph isomorphic to $G_i$, colored with the $i$th color for some $1\leq i\leq t$. We compute the exact values of the bipartite Ramsey numbers $BR(C_8,C_{2n})$ for $n\geq2$.

---

A characterization of rich c-partite (c > 7) tournaments without (c + 2)-cycles

Jie Zhang ; Zhilan Wang ; Jin Yan.

Let c be an integer. A c-partite tournament is an orientation of a complete c-partite graph. A c-partite tournament is rich if it is strong, and each partite set has at least two vertices. In 1996, Guo and Volkmann characterized the structure of all rich c-partite tournaments without (c + 1)-cycles, which solved a problem by Bondy. They also put forward a problem that what the structure of rich c-partite tournaments without (c + k)-cycles for some k>1 is. In this paper, we answer the question of Guo and Volkmann for k = 2.

---

On Mixed Cages

Geoffrey Exoo.

Mixed graphs have both directed and undirected edges. A mixed cage is a regular mixed graph of given girth with minimum possible order. In this paper mixed cages are studied. Upper bounds are obtained by general construction methods and computer searches.

---

Proving exact values for the $2$-limited broadcast domination number on grid graphs

Aaron Slobodin ; Gary MacGillivray ; Wendy Myrvold.

We establish exact values for the $2$-limited broadcast domination number of various grid graphs, in particular $C_m\square C_n$ for $3 \leq m \leq 6$ and all $n\geq m$, $P_m \square C_3$ for all $m \geq 3$, and $P_m \square C_n$ for $4\leq m \leq 5$ and all $n \geq m$. We also produce periodically optimal values for $P_m \square C_4$ and $P_m \square C_6$ for $m \geq 3$, $P_4 \square P_n$ for $n \geq 4$, and $P_5 \square P_n$ for $n \geq 5$. Our method completes an exhaustive case analysis and eliminates cases by combining tools from linear programming with various mathematical proof techniques.

---

Bears with Hats and Independence Polynomials

Václav Blažej ; Pavel Dvořák ; Michal Opler.

Consider the following hat guessing game. A bear sits on each vertex of a graph $G$, and a demon puts on each bear a hat colored by one of $h$ colors. Each bear sees only the hat colors of his neighbors. Based on this information only, each bear has to guess $g$ colors and he guesses correctly if his hat color is included in his guesses. The bears win if at least one bear guesses correctly for any hat arrangement. We introduce a new parameter - fractional hat chromatic number $\hat{\mu}$, arising from the hat guessing game. The parameter $\hat{\mu}$ is related to the hat chromatic number which has been studied before. We present a surprising connection between the hat guessing game and the independence polynomial of graphs. This connection allows us to compute the fractional hat chromatic number of chordal graphs in polynomial time, to bound fractional hat chromatic number by a function of maximum degree of $G$, and to compute the exact value of $\hat{\mu}$ of cliques, paths, and cycles.

---

Homomorphically Full Oriented Graphs

Thomas Bellitto ; Christopher Duffy ; Gary MacGillivray.

Homomorphically full graphs are those for which every homomorphic image is isomorphic to a subgraph. We extend the definition of homomorphically full to oriented graphs in two different ways. For the first of these, we show that homomorphically full oriented graphs arise as quasi-transitive orientations of homomorphically full graphs. This in turn yields an efficient recognition and construction algorithms for these homomorphically full oriented graphs. For the second one, we show that the related recognition problem is GI-hard, and that the problem of deciding if a graph admits a homomorphically full orientation is NP-complete. In doing so we show the problem of deciding if two given oriented cliques are isomorphic is GI-complete.

---

Maker-Breaker domination game on trees when Staller wins

Csilla Bujtás ; Pakanun Dokyeesun ; Sandi Klavžar.

In the Maker-Breaker domination game played on a graph $G$, Dominator's goal is to select a dominating set and Staller's goal is to claim a closed neighborhood of some vertex. We study the cases when Staller can win the game. If Dominator (resp., Staller) starts the game, then $\gamma_{\rm SMB}(G)$ (resp., $\gamma_{\rm SMB}'(G)$) denotes the minimum number of moves Staller needs to win. For every positive integer $k$, trees $T$ with $\gamma_{\rm SMB}'(T)=k$ are characterized and a general upper bound on $\gamma_{\rm SMB}'$ is proved. Let $S = S(n_1,\dots, n_\ell)$ be the subdivided star obtained from the star with $\ell$ edges by subdividing its edges $n_1-1, \ldots, n_\ell-1$ times, respectively. Then $\gamma_{\rm SMB}'(S)$ is determined in all the cases except when $\ell\ge 4$ and each $n_i$ is even. The simplest formula is obtained when there are at least two odd $n_i$s. If $n_1$ and $n_2$ are the two smallest such numbers, then $\gamma_{\rm SMB}'(S(n_1,\dots, n_\ell))=\lceil \log_2(n_1+n_2+1)\rceil$. For caterpillars, exact formulas for $\gamma_{\rm SMB}$ and for $\gamma_{\rm SMB}'$ are established.

---

Bounds on the Twin-Width of Product Graphs

William Pettersson ; John Sylvester.

Twin-width is a graph width parameter recently introduced by Bonnet, Kim, Thomassé & Watrigant. Given two graphs $G$ and $H$ and a graph product $\star$, we address the question: is the twin-width of $G\star H$ bounded by a function of the twin-widths of $G$ and $H$ and their maximum degrees? It is known that a bound of this type holds for strong products (Bonnet, Geniet, Kim, Thomassé & Watrigant; SODA 2021). We show that bounds of the same form hold for Cartesian, tensor/direct, corona, rooted, replacement, and zig-zag products. For the lexicographical product it is known that the twin-width of the product of two graphs is exactly the maximum of the twin-widths of the individual graphs (Bonnet, Kim, Reinald, Thomassé & Watrigant; IPEC 2021). In contrast, for the modular product we show that no bound can hold. In addition, we provide examples showing many of our bounds are tight, and give improved bounds for certain classes of graphs.

---

Gallai's Path Decomposition for 2-degenerate Graphs

Nevil Anto ; Manu Basavaraju.

Gallai's path decomposition conjecture states that if $G$ is a connected graph on $n$ vertices, then the edges of $G$ can be decomposed into at most $\lceil \frac{n }{2} \rceil$ paths. A graph is said to be an odd semi-clique if it can be obtained from a clique on $2k+1$ vertices by deleting at most $k-1$ edges. Bonamy and Perrett asked if the edges of every connected graph $G$ on $n$ vertices can be decomposed into at most $\lfloor \frac{n}{2} \rfloor$ paths unless $G$ is an odd semi-clique. A graph $G$ is said to be 2-degenerate if every subgraph of $G$ has a vertex of degree at most $2$. In this paper, we prove that the edges of any connected 2-degenerate graph $G$ on $n$ vertices can be decomposed into at most $\lfloor \frac{n }{2} \rfloor$ paths unless $G$ is a triangle.

---

Several Roman domination graph invariants on Kneser graphs

Tatjana Zec ; Milana Grbić.

This paper considers the following three Roman domination graph invariants on Kneser graphs: Roman domination, total Roman domination, and signed Roman domination. For Kneser graph $K_{n,k}$, we present exact values for Roman domination number $\gamma_{R}(K_{n,k})$ and total Roman domination number $\gamma_{tR}(K_{n,k})$ proving that for $n\geqslant k(k+1)$, $\gamma_{R}(K_{n,k}) =\gamma_{tR}(K_{n,k}) = 2(k+1)$. For signed Roman domination number $\gamma_{sR}(K_{n,k})$, the new lower and upper bounds for $K_{n,2}$ are provided: we prove that for $n\geqslant 12$, the lower bound is equal to 2, while the upper bound depends on the parity of $n$ and is equal to 3 if $n$ is odd, and equal to $5$ if $n$ is even. For graphs of smaller dimensions, exact values are found by applying exact methods from literature.

---

Rainbow vertex pair-pancyclicity of strongly edge-colored graphs

Peixue Zhao ; Fei Huang.

An edge-colored graph is \emph{rainbow }if no two edges of the graph have the same color. An edge-colored graph $G^c$ is called \emph{properly colored} if every two adjacent edges of $G^c$ receive distinct colors in $G^c$. A \emph{strongly edge-colored} graph is a proper edge-colored graph such that every path of length $3$ is rainbow. We call an edge-colored graph $G^c$ \emph{rainbow vertex pair-pancyclic} if any two vertices in $G^c$ are contained in a rainbow cycle of length $\ell$ for each $\ell$ with $3 \leq \ell \leq n$. In this paper, we show that every strongly edge-colored graph $G^c$ of order $n$ with minimum degree $\delta \geq \frac{2n}{3}+1$ is rainbow vertex pair-pancyclicity.

---

From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows

Cláudio Carvalho ; Jonas Costa ; Raul Lopes ; Ana Karolinna Maia ; Nicolas Nisse ; Cláudia Sales.

An s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow thatreaches every vertex in V(D) from s while loosing exactly one unit of flow in each vertex other thans. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity n − 1, a network Nadmits k arc-disjoint s-branching flows if and only if its associated digraph D contains k arc-disjoints-branchings. Thus a classical result by Edmonds stating that a digraph contains k arc-disjoints-branchings if and only if the indegree of every set X ⊆ V (D) \ {s} is at least k also characterizesthe existence of k arc-disjoint s-branching flows in those networks, suggesting that the larger thecapacities are, the closer an s-branching flow is from simply being an s-branching. This observationis further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomialalgorithm to find the flows (if they exist) when every arc has capacity n − c, for every fixed c ≥ 1,and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper,we investigate how a property that is a natural extension of the characterization by Edmonds’ relatesto the existence of k arc-disjoint s-branching flows in networks. Although this property is alwaysnecessary for the existence of the flows, we show that it is not always sufficient and that it is hardto decide if the desired flows exist even if we know beforehand that the network satisfies it. […]

---

Extremal problems of double stars

Ervin Győri ; Runze Wang ; Spencer Woolfson.

In a generalized Turán problem, two graphs $H$ and $F$ are given and the question is the maximum number of copies of $H$ in an $F$-free graph of order $n$. In this paper, we study the number of double stars $S_{k,l}$ in triangle-free graphs. We also study an opposite version of this question: what is the maximum number edges/triangles in graphs with double star type restrictions, which leads us to study two questions related to the extremal number of triangles or edges in graphs with degree-sum constraints over adjacent or non-adjacent vertices.

---

Destroying Multicolored Paths and Cycles in Edge-Colored Graphs

Nils Jakob Eckstein ; Niels Grüttemeier ; Christian Komusiewicz ; Frank Sommer.

We study the computational complexity of $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion. In these problems, one is given a $c$-edge-colored graph and wants to destroy all induced $c$-colored paths or cycles, respectively, on $\ell$ vertices by deleting at most $k$ edges. Herein, a path or cycle is $c$-colored if it contains edges of $c$ distinct colors. We show that $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion are NP-hard for each non-trivial combination of $c$ and $\ell$. We then analyze the parameterized complexity of these problems. We extend the notion of neighborhood diversity to edge-colored graphs and show that both problems are fixed-parameter tractable with respect to the colored neighborhood diversity of the input graph. We also provide hardness results to outline the limits of parameterization by the standard parameter solution size $k$. Finally, we consider bicolored input graphs and show a special case of $2$-Colored $P_4$ Deletion that can be solved in polynomial time.

---

Span of a Graph: Keeping the Safety Distance

Iztok Banič ; Andrej Taranenko.

Inspired by Lelek's idea from [Disjoint mappings and the span of spaces, Fund. Math. 55 (1964), 199 -- 214], we introduce the novel notion of the span of graphs. Using this, we solve the problem of determining the \emph{maximal safety distance} two players can keep at all times while traversing a graph. Moreover, their moves must be made with respect to certain move rules. For this purpose, we introduce different variants of a span of a given connected graph. All the variants model the maximum safety distance kept by two players in a graph traversal, where the players may only move with accordance to a specific set of rules, and their goal: visit either all vertices, or all edges. For each variant, we show that the solution can be obtained by considering only connected subgraphs of a graph product and the projections to the factors. We characterise graphs in which it is impossible to keep a positive safety distance at all moments in time. Finally, we present a polynomial time algorithm that determines the chosen span variant of a given graph.

---

Proximity, remoteness and maximum degree in graphs

Peter Dankelmann ; Sonwabile Mafunda ; Sufiyan Mallu.

The average distance of a vertex $v$ of a connected graph $G$ is the arithmetic mean of the distances from $v$ to all other vertices of $G$. The proximity $\pi(G)$ and the remoteness $\rho(G)$ of $G$ are the minimum and the maximum of the average distances of the vertices of $G$, respectively. In this paper, we give upper bounds on the remoteness and proximity for graphs of given order, minimum degree and maximum degree. Our bounds are sharp apart from an additive constant.

---

The 2-colouring problem for $(m,n)$-mixed graphs with switching is polynomial

Richard C Brewster ; Arnott Kidner ; Gary MacGillivray.

A mixed graph is a set of vertices together with an edge set and an arc set. An $(m,n)$-mixed graph $G$ is a mixed graph whose edges are each assigned one of $m$ colours, and whose arcs are each assigned one of $n$ colours. A \emph{switch} at a vertex $v$ of $G$ permutes the edge colours, the arc colours, and the arc directions of edges and arcs incident with $v$. The group of all allowed switches is $\Gamma$. Let $k \geq 1$ be a fixed integer and $\Gamma$ a fixed permutation group. We consider the problem that takes as input an $(m,n)$-mixed graph $G$ and asks if there a sequence of switches at vertices of $G$ with respect to $\Gamma$ so that the resulting $(m,n)$-mixed graph admits a homomorphism to an $(m,n)$-mixed graph on $k$ vertices. Our main result establishes this problem can be solved in polynomial time for $k \leq 2$, and is NP-hard for $k \geq 3$. This provides a step towards a general dichotomy theorem for the $\Gamma$-switchable homomorphism decision problem.

---

Improved product structure for graphs on surfaces

Marc Distel ; Robert Hickingbotham ; Tony Huynh ; David R. Wood.

Dujmovi\'c, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every graph $G$ with Euler genus $g$ there is a graph $H$ with treewidth at most 4 and a path $P$ such that $G\subseteq H \boxtimes P \boxtimes K_{\max\{2g,3\}}$. We improve this result by replacing "4" by "3" and with $H$ planar. We in fact prove a more general result in terms of so-called framed graphs. This implies that every $(g,d)$-map graph is contained in $ H \boxtimes P\boxtimes K_\ell$, for some planar graph $H$ with treewidth $3$, where $\ell=\max\{2g\lfloor \frac{d}{2} \rfloor,d+3\lfloor\frac{d}{2}\rfloor-3\}$. It also implies that every $(g,1)$-planar graph (that is, graphs that can be drawn in a surface of Euler genus $g$ with at most one crossing per edge) is contained in $H\boxtimes P\boxtimes K_{\max\{4g,7\}}$, for some planar graph $H$ with treewidth $3$.

---

On the monophonic rank of a graph

Mitre C. Dourado ; Vitor S. Ponciano ; Rômulo L. O. da Silva.

A set of vertices $S$ of a graph $G$ is {\em monophonically convex} if every induced path joining two vertices of $S$ is contained in $S$. The {\em monophonic convex hull of $S$}, $\langle S \rangle$, is the smallest monophonically convex set containing $S$. A set $S$ is {\em monophonic convexly independent} if $v \not\in \langle S - \{v\} \rangle$ for every $v \in S$. The {\em monophonic rank} of $G$ is the size of the largest monophonic convexly independent set of $G$. We present a characterization of the monophonic convexly independent sets. Using this result, we show how to determine the monophonic rank of graph classes like bipartite, cactus, triangle-free, and line graphs in polynomial time. Furthermore, we show that this parameter can computed in polynomial time for $1$-starlike graphs, i.e., for split graphs, and that its determination is $\NP$-complete for $k$-starlike graphs for any fixed $k \ge 2$, a subclass of chordal graphs. We also consider this problem on the graphs whose intersection graph of the maximal prime subgraphs is a tree.

---

On the domination number of $t$-constrained de Bruijn graphs

Tiziana Calamoneri ; Angelo Monti ; Blerina Sinaimeri.

Motivated by the work on the domination number of directed de Bruijn graphs and some of its generalizations, in this paper we introduce a natural generalization of de Bruijn graphs (directed and undirected), namely $t$-constrained de Bruijn graphs, where $t$ is a positive integer, and then study the domination number of these graphs. Within the definition of $t$-constrained de Bruijn graphs, de Bruijn and Kautz graphs correspond to 1-constrained and 2-constrained de Bruijn graphs, respectively. This generalization inherits many structural properties of de Bruijn graphs and may have similar applications in interconnection networks or bioinformatics. We establish upper and lower bounds for the domination number on $t$-constrained de Bruijn graphs both in the directed and in the undirected case. These bounds are often very close and in some cases we are able to find the exact value.

---

Further results on Hendry's Conjecture

Manuel Lafond ; Ben Seamone ; Rezvan Sherkati.

Recently, a conjecture due to Hendry was disproved which stated that every Hamiltonian chordal graph is cycle extendible. Here we further explore the conjecture, showing that it fails to hold even when a number of extra conditions are imposed. In particular, we show that Hendry's Conjecture fails for strongly chordal graphs, graphs with high connectivity, and if we relax the definition of "cycle extendible" considerably. We also consider the original conjecture from a subtree intersection model point of view, showing that a result of Abuieda et al is nearly best possible.

---

Tuza's Conjecture for Threshold Graphs

Marthe Bonamy ; Łukasz Bożyk ; Andrzej Grzesik ; Meike Hatzel ; Tomáš Masařík ; Jana Novotná ; Karolina Okrasa.

Tuza famously conjectured in 1981 that in a graph without k+1 edge-disjoint triangles, it suffices to delete at most 2k edges to obtain a triangle-free graph. The conjecture holds for graphs with small treewidth or small maximum average degree, including planar graphs. However, for dense graphs that are neither cliques nor 4-colorable, only asymptotic results are known. Here, we confirm the conjecture for threshold graphs, i.e. graphs that are both split graphs and cographs, and for co-chain graphs with both sides of the same size divisible by 4.

---

Asymptotically sharpening the $s$-Hamiltonian index bound

Sulin Song ; Lan Lei ; Yehong Shao ; Hong-Jian Lai.

For a non-negative integer $s\le |V(G)|-3$, a graph $G$ is $s$-Hamiltonian if the removal of any $k\le s$ vertices results in a Hamiltonian graph. Given a connected simple graph $G$ that is not isomorphic to a path, a cycle, or a $K_{1,3}$, let $\delta(G)$ denote the minimum degree of $G$, let $h_s(G)$ denote the smallest integer $i$ such that the iterated line graph $L^{i}(G)$ is $s$-Hamiltonian, and let $\ell(G)$ denote the length of the longest non-closed path $P$ in which all internal vertices have degree 2 such that $P$ is not both of length 2 and in a $K_3$. For a simple graph $G$, we establish better upper bounds for $h_s(G)$ as follows. \begin{equation*} h_s(G)\le \left\{ \begin{aligned} & \ell(G)+1, &&\mbox{ if }\delta(G)\le 2 \mbox{ and }s=0;\\ & \widetilde d(G)+2+\lceil \lg (s+1)\rceil, &&\mbox{ if }\delta(G)\le 2 \mbox{ and }s\ge 1;\\ & 2+\left\lceil\lg\frac{s+1}{\delta(G)-2}\right\rceil, && \mbox{ if } 3\le\delta(G)\le s+2;\\ & 2, &&{\rm otherwise}, \end{aligned} \right. \end{equation*} where $\widetilde d(G)$ is the smallest integer $i$ such that $\delta(L^i(G))\ge 3$. Consequently, when $s \ge 6$, this new upper bound for the $s$-hamiltonian index implies that $h_s(G) = o(\ell(G)+s+1)$ as $s \to \infty$. This sharpens the result, $h_s(G)\le\ell(G)+s+1$, obtained by Zhang et al. in [Discrete Math., 308 (2008) 4779-4785].

---

Maker-Breaker total domination game on cubic graphs

Jovana Forcan ; Mirjana Mikalački.

We study Maker--Breaker total domination game played by two players, Dominator and Staller, on the connected cubic graphs. Staller (playing the role of Maker) wins if she manages to claim an open neighbourhood of a vertex. Dominator wins otherwise (i.e.\ if he can claim a total dominating set of a graph). For certain graphs on $n\geq 6$ vertices, we give the characterization on those which are Dominator's win and those which are Staller's win.

---

Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree

Julien Baste ; Stefan Ehard ; Dieter Rautenbach.

We consider a non-monotone activation process $(X_t)_{t\in\{ 0,1,2,\ldots\}}$ on a graph $G$, where $X_0\subseteq V(G)$, $X_t=\{ u\in V(G):|N_G(u)\cap X_{t-1}|\geq \tau(u)\}$ for every positive integer $t$, and $\tau:V(G)\to \mathbb{Z}$ is a threshold function. The set $X_0$ is a so-called non-monotone target set for $(G,\tau)$ if there is some $t_0$ such that $X_t=V(G)$ for every $t\geq t_0$. Ben-Zwi, Hermelin, Lokshtanov, and Newman [Discrete Optimization 8 (2011) 87-96] asked whether a target set of minimum order can be determined efficiently if $G$ is a tree. We answer their question in the affirmative for threshold functions $\tau$ satisfying $\tau(u)\in \{ 0,1,d_G(u)\}$ for every vertex~$u$. For such restricted threshold functions, we give a characterization of target sets that allows to show that the minimum target set problem remains NP-hard for planar graphs of maximum degree $3$ but is efficiently solvable for graphs of bounded treewidth.

---

Separating layered treewidth and row treewidth

Prosenjit Bose ; Vida Dujmović ; Mehrnoosh Javarsineh ; Pat Morin ; David R. Wood.

Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems. It follows from the definitions that the layered treewidth of a graph is at most its row treewidth plus 1. Moreover, a minor-closed class has bounded layered treewidth if and only if it has bounded row treewidth. However, it has been open whether row treewidth is bounded by a function of layered treewidth. This paper answers this question in the negative. In particular, for every integer $k$ we describe a graph with layered treewidth 1 and row treewidth $k$. We also prove an analogous result for layered pathwidth and row pathwidth.

---

The Neighborhood Polynomial of Chordal Graphs

Helena Bergold ; Winfried Hochstättler ; Uwe Mayer.

We study the neighborhood polynomial and the complexity of its computation for chordal graphs. The neighborhood polynomial of a graph is the generating function of subsets of its vertices that have a common neighbor. We introduce a parameter for chordal graphs called anchor width and an algorithm to compute the neighborhood polynomial which runs in polynomial time if the anchor width is polynomially bounded. The anchor width is the maximal number of different sub-cliques of a clique which appear as a common neighborhood. Furthermore we study the anchor width for chordal graphs and some subclasses such as chordal comparability graphs and chordal graphs with bounded leafage. the leafage of a chordal graphs is the minimum number of leaves in the host tree of a subtree representation. We show that the anchor width of a chordal graph is at most $n^{\ell}$ where $\ell$ denotes the leafage. This shows that for some subclasses computing the neighborhood polynomial is possible in polynomial time while it is NP-hard for general chordal graphs.

---

Domination in Knödel Graphs

Jesse Racicot ; Giovanni Rosso.

Given a graph and an integer $k$, it is an NP-complete problem to decide whether there is a dominating set of size at most $k$. In this paper we study this problem for the Knödel Graph on $n$ vertices using elementary number theory techniques. In particular, we show an explicit upper bound for the domination number of the Knödel Graph on $n$ vertices any time that we can find a prime number $p$ dividing $n$ for which $2$ is a primitive root.

---

On the Erdős-Pósa property for immersions and topological minors in tournaments

Łukasz Bożyk ; Michał Pilipczuk.

We consider the Erdős-Pósa property for immersions and topological minors in tournaments. We prove that for every simple digraph $H$, $k\in \mathbb{N}$, and tournament $T$, the following statements hold: (i) If in $T$ one cannot find $k$ arc-disjoint immersion copies of $H$, then there exists a set of $\mathcal{O}_H(k^3)$ arcs that intersects all immersion copies of $H$ in $T$. (ii) If in $T$ one cannot find $k$ vertex-disjoint topological minor copies of $H$, then there exists a set of $\mathcal{O}_H(k\log k)$ vertices that intersects all topological minor copies of $H$ in $T$. This improves the results of Raymond [DMTCS '18], who proved similar statements under the assumption that $H$ is strongly connected.

---

Notes on Equitable Partitions into Matching Forests in Mixed Graphs and into $b$-branchings in Digraphs

Kenjiro Takazawa.

An equitable partition into branchings in a digraph is a partition of the arc set into branchings such that the sizes of any two branchings differ at most by one. For a digraph whose arc set can be partitioned into $k$ branchings, there always exists an equitable partition into $k$ branchings. In this paper, we present two extensions of equitable partitions into branchings in digraphs: those into matching forests in mixed graphs; and into $b$-branchings in digraphs. For matching forests, Király and Yokoi (2022) considered a tricriteria equitability based on the sizes of the matching forest, and the matching and branching therein. In contrast to this, we introduce a single-criterion equitability based on the number of covered vertices, which is plausible in the light of the delta-matroid structure of matching forests. While the existence of this equitable partition can be derived from a lemma in Király and Yokoi, we present its direct and simpler proof. For $b$-branchings, we define an equitability notion based on the size of the $b$-branching and the indegrees of all vertices, and prove that an equitable partition always exists. We then derive the integer decomposition property of the associated polytopes.

---

Constant Congestion Brambles

Meike Hatzel ; Pawel Komosa ; Marcin Pilipczuk ; Manuel Sorge.

A bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one endpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble. Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the maximum order of a bramble in an undirected graph $G$ equals one plus the treewidth of $G$. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree $n$-vertex expander a bramble of order $\Omega(n^{1/2+\delta})$ requires size exponential in $\Omega(n^{2\delta})$ for any fixed $\delta \in (0,\frac{1}{2}]$. On the other hand, the combination of results of Grohe and Marx and Chekuri and Chuzhoy shows that a graph of treewidth $k$ admits a bramble of order $\widetilde{\Omega}(k^{1/2})$ and size $\widetilde{\mathcal{O}}(k^{3/2})$. ($\widetilde{\Omega}$ and $\widetilde{\mathcal{O}}$ hide polylogarithmic factors and divisors, respectively.) In this note, we first sharpen the second bound by proving that every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2})$ and congestion $2$, i.e., every vertex of $G$ is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we […]

---

Determining Number of Kneser Graphs: Exact Values and Improved Bounds

Angsuman Das ; Hiranya Kishore Dey.

The determining number of a graph $G = (V,E)$ is the minimum cardinality of a set $S\subseteq V$ such that pointwise stabilizer of $S$ under the action of $Aut(G)$ is trivial. In this paper, we provide some improved upper and lower bounds on the determining number of Kneser graphs. Moreover, we provide the exact value of the determining number for some subfamilies of Kneser graphs.

---

On the Connectivity of Token Graphs of Trees

Ruy Fabila-Monroy ; Jesús Leaños ; Ana Laura Trujillo-Negrete.

Let $k$ and $n$ be integers such that $1\leq k \leq n-1$, and let $G$ be a simple graph of order $n$. The $k$-token graph $F_k(G)$ of $G$ is the graph whose vertices are the $k$-subsets of $V(G)$, where two vertices are adjacent in $F_k(G)$ whenever their symmetric difference is an edge of $G$. In this paper we show that if $G$ is a tree, then the connectivity of $F_k(G)$ is equal to the minimum degree of $F_k(G)$.

---

Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs

Márcia R. Cappelle ; Erika Coelho ; Les R. Foulds ; Humberto J. Longo.

Let $G=(V(G),E(G))$ be a finite simple undirected graph with vertex set $V(G)$, edge set $E(G)$ and vertex subset $S\subseteq V(G)$. $S$ is termed \emph{open-dominating} if every vertex of $G$ has at least one neighbor in $S$, and \emph{open-independent, open-locating-dominating} (an $OLD_{oind}$-set for short) if no two vertices in $G$ have the same set of neighbors in $S$, and each vertex in $S$ is open-dominated exactly once by $S$. The problem of deciding whether or not $G$ has an $OLD_{oind}$-set has important applications that have been reported elsewhere. As the problem is known to be $\mathcal{NP}$-complete, it appears to be notoriously difficult as we show that its complexity remains the same even for just planar bipartite graphs of maximum degree five and girth six, and also for planar subcubic graphs of girth nine. Also, we present characterizations of both $P_4$-tidy graphs and the complementary prisms of cographs that have an $OLD_{oind}$-set.

---

An explicit construction of graphs of bounded degree that are far from being Hamiltonian

Isolde Adler ; Noleen Köhler.

Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an impressive amount of research has been dedicated to identifying classes of graphs that allow Hamiltonian cycles, and to related questions. The corresponding decision problem, that asks whether a given graph is Hamiltonian (i.\,e.\ admits a Hamiltonian cycle), is one of Karp's famous NP-complete problems. In this paper we study graphs of bounded degree that are \emph{far} from being Hamiltonian, where a graph $G$ on $n$ vertices is \emph{far} from being Hamiltonian, if modifying a constant fraction of $n$ edges is necessary to make $G$ Hamiltonian. We give an explicit deterministic construction of a class of graphs of bounded degree that are locally Hamiltonian, but (globally) far from being Hamiltonian. Here, \emph{locally Hamiltonian} means that every subgraph induced by the neighbourhood of a small vertex set appears in some Hamiltonian graph. More precisely, we obtain graphs which differ in $\Theta(n)$ edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected in the neighbourhood of $o(n)$ vertices. Our class of graphs yields a class of hard instances for one-sided error property testers with linear query complexity. It is known that any property tester (even with two-sided error) requires a linear number of queries to test Hamiltonicity (Yoshida, Ito, 2010). This is proved via a randomised construction of hard instances. In contrast, our construction is deterministic. So far only […]

---

Upward-closed hereditary families in the dominance order

Michael D. Barrus ; Jean A. Guillaume.

The majorization relation orders the degree sequences of simple graphs into posets called dominance orders. As shown by Ruch and Gutman (1979) and Merris (2002), the degree sequences of threshold and split graphs form upward-closed sets within the dominance orders they belong to, i.e., any degree sequence majorizing a split or threshold sequence must itself be split or threshold, respectively. Motivated by the fact that threshold graphs and split graphs have characterizations in terms of forbidden induced subgraphs, we define a class $\mathcal{F}$ of graphs to be dominance monotone if whenever no realization of $e$ contains an element $\mathcal{F}$ as an induced subgraph, and $d$ majorizes $e$, then no realization of $d$ induces an element of $\mathcal{F}$. We present conditions necessary for a set of graphs to be dominance monotone, and we identify the dominance monotone sets of order at most 3.

---

Extremal digraphs on Meyniel-type condition for hamiltonian cycles in balanced bipartite digraphs

Ruixia Wang ; Linxin Wu ; Wei Meng.

Let $D$ be a strong balanced digraph on $2a$ vertices. Adamus et al. have proved that $D$ is hamiltonian if $d(u)+d(v)\ge 3a$ whenever $uv\notin A(D)$ and $vu\notin A(D)$. The lower bound $3a$ is tight. In this paper, we shall show that the extremal digraph on this condition is two classes of digraphs that can be clearly characterized. Moreover, we also show that if $d(u)+d(v)\geq 3a-1$ whenever $uv\notin A(D)$ and $vu\notin A(D)$, then $D$ is traceable. The lower bound $3a-1$ is tight.

---

Upper paired domination versus upper domination

Hadi Alizadeh ; Didem Gözüpek.

A paired dominating set $P$ is a dominating set with the additional property that $P$ has a perfect matching. While the maximum cardainality of a minimal dominating set in a graph $G$ is called the upper domination number of $G$, denoted by $\Gamma(G)$, the maximum cardinality of a minimal paired dominating set in $G$ is called the upper paired domination number of $G$, denoted by $\Gamma_{pr}(G)$. By Henning and Pradhan (2019), we know that $\Gamma_{pr}(G)\leq 2\Gamma(G)$ for any graph $G$ without isolated vertices. We focus on the graphs satisfying the equality $\Gamma_{pr}(G)= 2\Gamma(G)$. We give characterizations for two special graph classes: bipartite and unicyclic graphs with $\Gamma_{pr}(G)= 2\Gamma(G)$ by using the results of Ulatowski (2015). Besides, we study the graphs with $\Gamma_{pr}(G)= 2\Gamma(G)$ and a restricted girth. In this context, we provide two characterizations: one for graphs with $\Gamma_{pr}(G)= 2\Gamma(G)$ and girth at least 6 and the other for $C_3$-free cactus graphs with $\Gamma_{pr}(G)= 2\Gamma(G)$. We also pose the characterization of the general case of $C_3$-free graphs with $\Gamma_{pr}(G)= 2\Gamma(G)$ as an open question.

---

The treewidth of 2-section of hypergraphs

Ke Liu ; Mei Lu.

Let $H=(V,F)$ be a simple hypergraph without loops. $H$ is called linear if $|f\cap g|\le 1$ for any $f,g\in F$ with $f\not=g$. The $2$-section of $H$, denoted by $[H]_2$, is a graph with $V([H]_2)=V$ and for any $ u,v\in V([H]_2)$, $uv\in E([H]_2)$ if and only if there is $ f\in F$ such that $u,v\in f$. The treewidth of a graph is an important invariant in structural and algorithmic graph theory. In this paper, we consider the treewidth of the $2$-section of a linear hypergraph. We will use the minimum degree, maximum degree, anti-rank and average rank of a linear hypergraph to determine the upper and lower bounds of the treewidth of its $2$-section. Since for any graph $G$, there is a linear hypergraph $H$ such that $[H]_2\cong G$, we provide a method to estimate the bound of treewidth of graph by the parameters of the hypergraph.

---

List-antimagic labeling of vertex-weighted graphs

Zhanar Berikkyzy ; Axel Brandt ; Sogol Jahanbekam ; Victor Larsen ; Danny Rorabaugh.

A graph $G$ is $k$-$weighted-list-antimagic$ if for any vertex weighting $\omega\colon V(G)\to\mathbb{R}$ and any list assignment $L\colon E(G)\to2^{\mathbb{R}}$ with $|L(e)|\geq |E(G)|+k$ there exists an edge labeling $f$ such that $f(e)\in L(e)$ for all $e\in E(G)$, labels of edges are pairwise distinct, and the sum of the labels on edges incident to a vertex plus the weight of that vertex is distinct from the sum at every other vertex. In this paper we prove that every graph on $n$ vertices having no $K_1$ or $K_2$ component is $\lfloor{\frac{4n}{3}}\rfloor$-weighted-list-antimagic. An oriented graph $G$ is $k$-$oriented-antimagic$ if there exists an injective edge labeling from $E(G)$ into $\{1,\dotsc,|E(G)|+k\}$ such that the sum of the labels on edges incident to and oriented toward a vertex minus the sum of the labels on edges incident to and oriented away from that vertex is distinct from the difference of sums at every other vertex. We prove that every graph on $n$ vertices with no $K_1$ component admits an orientation that is $\lfloor{\frac{2n}{3}}\rfloor$-oriented-antimagic.

---

Fast Diameter Computation within Split Graphs

Guillaume Ducoffe ; Michel Habib ; Laurent Viennot.

When can we compute the diameter of a graph in quasi linear time? We address this question for the class of {\em split graphs}, that we observe to be the hardest instances for deciding whether the diameter is at most two. We stress that although the diameter of a non-complete split graph can only be either $2$ or $3$, under the Strong Exponential-Time Hypothesis (SETH) we cannot compute the diameter of an $n$-vertex $m$-edge split graph in less than quadratic time -- in the size $n+m$ of the input. Therefore it is worth to study the complexity of diameter computation on {\em subclasses} of split graphs, in order to better understand the complexity border. Specifically, we consider the split graphs with bounded {\em clique-interval number} and their complements, with the former being a natural variation of the concept of interval number for split graphs that we introduce in this paper. We first discuss the relations between the clique-interval number and other graph invariants such as the classic interval number of graphs, the treewidth, the {\em VC-dimension} and the {\em stabbing number} of a related hypergraph. Then, in part based on these above relations, we almost completely settle the complexity of diameter computation on these subclasses of split graphs: - For the $k$-clique-interval split graphs, we can compute their diameter in truly subquadratic time if $k={\cal O}(1)$, and even in quasi linear time if $k=o(\log{n})$ and in addition a corresponding ordering of the […]

---

Five results on maximizing topological indices in graphs

Stijn Cambie.

In this paper, we prove a collection of results on graphical indices. We determine the extremal graphs attaining the maximal generalized Wiener index (e.g. the hyper-Wiener index) among all graphs with given matching number or independence number. This generalizes some work of Dankelmann, as well as some work of Chung. We also show alternative proofs for two recents results on maximizing the Wiener index and external Wiener index by deriving it from earlier results. We end with proving two conjectures. We prove that the maximum for the difference of the Wiener index and the eccentricity is attained by the path if the order $n$ is at least $9$ and that the maximum weighted Szeged index of graphs of given order is attained by the balanced complete bipartite graphs.

---

On the genera of polyhedral embeddings of cubic graph

Gunnar Brinkmann ; Thomas Tucker ; Nico Van Cleemput.

In this article we present theoretical and computational results on the existence of polyhedral embeddings of graphs. The emphasis is on cubic graphs. We also describe an efficient algorithm to compute all polyhedral embeddings of a given cubic graph and constructions for cubic graphs with some special properties of their polyhedral embeddings. Some key results are that even cubic graphs with a polyhedral embedding on the torus can also have polyhedral embeddings in arbitrarily high genus, in fact in a genus {\em close} to the theoretical maximum for that number of vertices, and that there is no bound on the number of genera in which a cubic graph can have a polyhedral embedding. While these results suggest a large variety of polyhedral embeddings, computations for up to 28 vertices suggest that by far most of the cubic graphs do not have a polyhedral embedding in any genus and that the ratio of these graphs is increasing with the number of vertices.

---

The structure and the list 3-dynamic coloring of outer-1-planar graphs

Yan Li ; Xin Zhang.

An outer-1-planar graph is a graph admitting a drawing in the plane so that all vertices appear in the outer region of the drawing and every edge crosses at most one other edge. This paper establishes the local structure of outer-1-planar graphs by proving that each outer-1-planar graph contains one of the seventeen fixed configurations, and the list of those configurations is minimal in the sense that for each fixed configuration there exist outer-1-planar graphs containing this configuration that do not contain any of another sixteen configurations. There are two interesting applications of this structural theorem. First of all, we conclude that every (resp. maximal) outer-1-planar graph of minimum degree at least 2 has an edge with the sum of the degrees of its two end-vertices being at most 9 (resp. 7), and this upper bound is sharp. On the other hand, we show that the list 3-dynamic chromatic number of every outer-1-planar graph is at most 6, and this upper bound is best possible.

---

A note on tight cuts in matching-covered graphs

Xiao Zhao ; Sheng Chen.

Edmonds, Lovász, and Pulleyblank showed that if a matching covered graph has a nontrivial tight cut, then it also has a nontrivial ELP-cut. Carvalho et al. gave a stronger conjecture: if a matching covered graph has a nontrivial tight cut $C$, then it also has a nontrivial ELP-cut that does not cross $C$. Chen, et al gave a proof of the conjecture. This note is inspired by the paper of Carvalho et al. We give a simplified proof of the conjecture, and prove the following result which is slightly stronger than the conjecture: if a nontrivial tight cut $C$ of a matching covered graph $G$ is not an ELP-cut, then there is a sequence $G_1=G, G_2,\ldots,G_r, r\geq2$ of matching covered graphs, such that for $i=1, 2,\ldots, r-1$, $G_i$ has an ELP-cut $C_i$, and $G_{i+1}$ is a $C_i$-contraction of $G_i$, and $C$ is a $2$-separation cut of $G_r$.

---

Destroying Bicolored $P_3$s by Deleting Few Edges

Niels Grüttemeier ; Christian Komusiewicz ; Jannik Schestag ; Frank Sommer.

We introduce and study the Bicolored $P_3$ Deletion problem defined as follows. The input is a graph $G=(V,E)$ where the edge set $E$ is partitioned into a set $E_r$ of red edges and a set $E_b$ of blue edges. The question is whether we can delete at most $k$ edges such that $G$ does not contain a bicolored $P_3$ as an induced subgraph. Here, a bicolored $P_3$ is a path on three vertices with one blue and one red edge. We show that Bicolored $P_3$ Deletion is NP-hard and cannot be solved in $2^{o(|V|+|E|)}$ time on bounded-degree graphs if the ETH is true. Then, we show that Bicolored $P_3$ Deletion is polynomial-time solvable when $G$ does not contain a bicolored $K_3$, that is, a triangle with edges of both colors. Moreover, we provide a polynomial-time algorithm for the case that $G$ contains no blue $P_3$, red $P_3$, blue $K_3$, and red $K_3$. Finally, we show that Bicolored $P_3$ Deletion can be solved in $ O(1.84^k\cdot |V| \cdot |E|)$ time and that it admits a kernel with $ O(k\Delta\min(k,\Delta))$ vertices, where $\Delta$ is the maximum degree of $G$.

---

Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees

Marc Hellmuth ; Carsten R. Seemann ; Peter F. Stadler.

Binary relations derived from labeled rooted trees play an import role in mathematical biology as formal models of evolutionary relationships. The (symmetrized) Fitch relation formalizes xenology as the pairs of genes separated by at least one horizontal transfer event. As a natural generalization, we consider symmetrized Fitch maps, that is, symmetric maps $\varepsilon$ that assign a subset of colors to each pair of vertices in $X$ and that can be explained by a tree $T$ with edges that are labeled with subsets of colors in the sense that the color $m$ appears in $\varepsilon(x,y)$ if and only if $m$ appears in a label along the unique path between $x$ and $y$ in $T$. We first give an alternative characterization of the monochromatic case and then give a characterization of symmetrized Fitch maps in terms of compatibility of a certain set of quartets. We show that recognition of symmetrized Fitch maps is NP-complete. In the restricted case where $|\varepsilon(x,y)|\leq 1$ the problem becomes polynomial, since such maps coincide with class of monochromatic Fitch maps whose graph-representations form precisely the class of complete multi-partite graphs.

---

Wiener index in graphs with given minimum degree and maximum degree

Peter Dankelmann ; Alex Alochukwu.

Let $G$ be a connected graph of order $n$.The Wiener index $W(G)$ of $G$ is the sum of the distances between all unordered pairs of vertices of $G$. In this paper we show that the well-known upper bound $\big( \frac{n}{\delta+1}+2\big) {n \choose 2}$ on the Wiener index of a graph of order $n$ and minimum degree $\delta$ [M. Kouider, P. Winkler, Mean distance and minimum degree. J. Graph Theory 25 no. 1 (1997)] can be improved significantly if the graph contains also a vertex of large degree. Specifically, we give the asymptotically sharp bound $W(G) \leq {n-\Delta+\delta \choose 2} \frac{n+2\Delta}{\delta+1}+ 2n(n-1)$ on the Wiener index of a graph $G$ of order $n$, minimum degree $\delta$ and maximum degree $\Delta$. We prove a similar result for triangle-free graphs, and we determine a bound on the Wiener index of $C_4$-free graphs of given order, minimum and maximum degree and show that it is, in some sense, best possible.

---

On the existence and non-existence of improper homomorphisms of oriented and $2$-edge-coloured graphs to reflexive targets

Christopher Duffy ; Sonja Linghui Shan.

We consider non-trivial homomorphisms to reflexive oriented graphs in which some pair of adjacent vertices have the same image. Using a notion of convexity for oriented graphs, we study those oriented graphs that do not admit such homomorphisms. We fully classify those oriented graphs with tree-width $2$ that do not admit such homomorphisms and show that it is NP-complete to decide if a graph admits an orientation that does not admit such homomorphisms. We prove analogous results for $2$-edge-coloured graphs. We apply our results on oriented graphs to provide a new tool in the study of chromatic number of orientations of planar graphs -- a long-standing open problem.

---

Wiener Index and Remoteness in Triangulations and Quadrangulations

Éva Czabarka ; Peter Dankelmann ; Trevor Olsen ; László A. Székely.

Let $G$ be a a connected graph. The Wiener index of a connected graph is the sum of the distances between all unordered pairs of vertices. We provide asymptotic formulae for the maximum Wiener index of simple triangulations and quadrangulations with given connectivity, as the order increases, and make conjectures for the extremal triangulations and quadrangulations based on computational evidence. If $\overline{\sigma}(v)$ denotes the arithmetic mean of the distances from $v$ to all other vertices of $G$, then the remoteness of $G$ is defined as the largest value of $\overline{\sigma}(v)$ over all vertices $v$ of $G$. We give sharp upper bounds on the remoteness of simple triangulations and quadrangulations of given order and connectivity.

---

Efficient enumeration of non-isomorphic interval graphs

Patryk Mikos.

Recently, Yamazaki et al. provided an algorithm that enumerates all non-isomorphic interval graphs on $n$ vertices with an $O(n^4)$ time delay. In this paper, we improve their algorithm and achieve $O(n^3 \log n)$ time delay. We also extend the catalog of these graphs providing a list of all non-isomorphic interval graphs for all $n$ up to $15$.

---

On BMRN*-colouring of planar digraphs

Julien Bensmail ; Foivos Fioravantes.

In a recent work, Bensmail, Blanc, Cohen, Havet and Rocha, motivated by applications for TDMA scheduling problems, have introduced the notion of BMRN*-colouring of digraphs, which is a type of arc-colouring with particular colouring constraints. In particular, they gave a special focus to planar digraphs. They notably proved that every planar digraph can be 8-BMRN*-coloured, while there exist planar digraphs for which 7 colours are needed in a BMRN*-colouring. They also proved that the problem of deciding whether a planar digraph can be 3-BMRN*-coloured is NP-hard. In this work, we pursue these investigations on planar digraphs, in particular by answering some of the questions left open by the authors in that seminal work. We exhibit planar digraphs needing 8 colours to be BMRN*-coloured, thus showing that the upper bound of Bensmail, Blanc, Cohen, Havet and Rocha cannot be decreased in general. We also generalize their complexity result by showing that the problem of deciding whether a planar digraph can be k-BMRN*-coloured is NP-hard for every k ∈ {3,...,6}. Finally, we investigate the connection between the girth of a planar digraphs and the least number of colours in its BMRN*-colourings.

---

A new sufficient condition for a Digraph to be Hamiltonian-A proof of Manoussakis Conjecture

Samvel Kh. Darbinyan.

Y. Manoussakis (J. Graph Theory 16, 1992, 51-59) proposed the following conjecture. \noindent\textbf{Conjecture}. {\it Let $D$ be a 2-strongly connected digraph of order $n$ such that for all distinct pairs of non-adjacent vertices $x$, $y$ and $w$, $z$, we have $d(x)+d(y)+d(w)+d(z)\geq 4n-3$. Then $D$ is Hamiltonian.} In this paper, we confirm this conjecture. Moreover, we prove that if a digraph $D$ satisfies the conditions of this conjecture and has a pair of non-adjacent vertices $\{x,y\}$ such that $d(x)+d(y)\leq 2n-4$, then $D$ contains cycles of all lengths $3, 4, \ldots , n$.

---

A Note on Graphs of Dichromatic Number 2

Raphael Steiner.

Neumann-Lara and Škrekovski conjectured that every planar digraph is 2-colourable. We show that this conjecture is equivalent to the more general statement that all oriented K_5-minor-free graphs are 2-colourable.

---

The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs

Xiao-Lu Gao ; Shou-Jun Xu.

A graph $G$ is a cocomparability graph if there exists an acyclic transitive orientation of the edges of its complement graph $\overline{G}$. LBFS$^{+}$ is a variant of the generic Lexicographic Breadth First Search (LBFS), which uses a specific tie-breaking mechanism. Starting with some ordering $\sigma_{0}$ of $G$, let $\{\sigma_{i}\}_{i\geq 1}$ be the sequence of orderings such that $\sigma_{i}=$LBFS$^{+}(G, \sigma_{i-1})$. The LexCycle($G$) is defined as the maximum length of a cycle of vertex orderings of $G$ obtained via such a sequence of LBFS$^{+}$ sweeps. Dusart and Habib conjectured in 2017 that LexCycle($G$)=2 if $G$ is a cocomparability graph and proved it holds for interval graphs. In this paper, we show that LexCycle($G$)=2 if $G$ is a $\overline{P_{2}\cup P_{3}}$-free cocomparability graph, where a $\overline{P_{2}\cup P_{3}}$ is the graph whose complement is the disjoint union of $P_{2}$ and $P_{3}$. As corollaries, it's applicable for diamond-free cocomparability graphs, cocomparability graphs with girth at least 4, as well as interval graphs.

---

Two lower bounds for $p$-centered colorings

Loïc Dubois ; Gwenaël Joret ; Guillem Perarnau ; Marcin Pilipczuk ; François Pitois.

Given a graph $G$ and an integer $p$, a coloring $f : V(G) \to \mathbb{N}$ is \emph{$p$-centered} if for every connected subgraph $H$ of $G$, either $f$ uses more than $p$ colors on $H$ or there is a color that appears exactly once in $H$. The notion of $p$-centered colorings plays a central role in the theory of sparse graphs. In this note we show two lower bounds on the number of colors required in a $p$-centered coloring. First, we consider monotone classes of graphs whose shallow minors have average degree bounded polynomially in the radius, or equivalently (by a result of Dvo\v{r}ák and Norin), admitting strongly sublinear separators. We construct such a class such that $p$-centered colorings require a number of colors super-polynomial in $p$. This is in contrast with a recent result of Pilipczuk and Siebertz, who established a polynomial upper bound in the special case of graphs excluding a fixed minor. Second, we consider graphs of maximum degree $\Delta$. D\k{e}bski, Felsner, Micek, and Schröder recently proved that these graphs have $p$-centered colorings with $O(\Delta^{2-1/p} p)$ colors. We show that there are graphs of maximum degree $\Delta$ that require $\Omega(\Delta^{2-1/p} p \ln^{-1/p}\Delta)$ colors in any $p$-centered coloring, thus matching their upper bound up to a logarithmic factor.

---

Even cycles and perfect matchings in claw-free plane graphs

Shanshan Zhang ; Xiumei Wang ; Jinjiang Yuan.

Lov{á}sz showed that a matching covered graph $G$ has an ear decomposition starting with an arbitrary edge of $G$. Let $G$ be a graph which has a perfect matching. We call $G$ cycle-nice if for each even cycle $C$ of $G$, $G-V(C)$ has a perfect matching. If $G$ is a cycle-nice matching covered graph, then $G$ has ear decompositions starting with an arbitrary even cycle of $G$. In this paper, we characterize cycle-nice claw-free plane graphs. We show that the only cycle-nice simple 3-connected claw-free plane graphs are $K_4$, $W_5$ and $\overline C_6$. Furthermore, every cycle-nice 2-connected claw-free plane graph can be obtained from a graph in the family ${\cal F}$ by a sequence of three types of operations, where ${\cal F}$ consists of even cycles, a diamond, $K_4$, and $\overline C_6$.

---

(Open) packing number of some graph products

Doost Ali Mojdeh ; Iztok Peterin ; Babak Samadi ; Ismael G. Yero.

The packing number of a graph $G$ is the maximum number of closed neighborhoods of vertices in $G$ with pairwise empty intersections. Similarly, the open packing number of $G$ is the maximum number of open neighborhoods in $G$ with pairwise empty intersections. We consider the packing and open packing numbers on graph products. In particular we give a complete solution with respect to some properties of factors in the case of lexicographic and rooted products. For Cartesian, strong and direct products, we present several lower and upper bounds on these parameters.

---

The agreement distance of unrooted phylogenetic networks

Jonathan Klawitter.

A rearrangement operation makes a small graph-theoretical change to a phylogenetic network to transform it into another one. For unrooted phylogenetic trees and networks, popular rearrangement operations are tree bisection and reconnection (TBR) and prune and regraft (PR) (called subtree prune and regraft (SPR) on trees). Each of these operations induces a metric on the sets of phylogenetic trees and networks. The TBR-distance between two unrooted phylogenetic trees $T$ and $T'$ can be characterised by a maximum agreement forest, that is, a forest with a minimum number of components that covers both $T$ and $T'$ in a certain way. This characterisation has facilitated the development of fixed-parameter tractable algorithms and approximation algorithms. Here, we introduce maximum agreement graphs as a generalisations of maximum agreement forests for phylogenetic networks. While the agreement distance -- the metric induced by maximum agreement graphs -- does not characterise the TBR-distance of two networks, we show that it still provides constant-factor bounds on the TBR-distance. We find similar results for PR in terms of maximum endpoint agreement graphs.

---

The Complexity of Helly-$B_{1}$ EPG Graph Recognition

Claudson F. Bornstein ; Martin Charles Golumbic ; Tanilson D. Santos ; Uéverton S. Souza ; Jayme L. Szwarcfiter.

Golumbic, Lipshteyn, and Stern defined in 2009 the class of EPG graphs, the intersection graph class of edge paths on a grid. An EPG graph $G$ is a graph that admits a representation where its vertices correspond to paths in a grid $Q$, such that two vertices of $G$ are adjacent if and only if their corresponding paths in $Q$ have a common edge. If the paths in the representation have at most $k$ bends, we say that it is a $B_k$-EPG representation. A collection $C$ of sets satisfies the Helly property when every sub-collection of $C$ that is pairwise intersecting has at least one common element. In this paper, we show that given a graph $G$ and an integer $k$, the problem of determining whether $G$ admits a $B_k$-EPG representation whose edge-intersections of paths satisfy the Helly property, so-called Helly-$B_k$-EPG representation, is in NP, for every $k$ bounded by a polynomial function of $|V(G)|$. Moreover, we show that the problem of recognizing Helly-$B_1$-EPG graphs is NP-complete, and it remains NP-complete even when restricted to 2-apex and 3-degenerate graphs.

---

Antifactors of regular bipartite graphs

Hongliang Lu ; Wei Wang ; Juan Yan.

Let $G=(X,Y;E)$ be a bipartite graph, where $X$ and $Y$ are color classes and $E$ is the set of edges of $G$. Lovász and Plummer \cite{LoPl86} asked whether one can decide in polynomial time that a given bipartite graph $G=(X,Y; E)$ admits a 1-anti-factor, that is subset $F$ of $E$ such that $d_F(v)=1$ for all $v\in X$ and $d_F(v)\neq 1$ for all $v\in Y$. Cornuéjols \cite{CHP} answered this question in the affirmative. Yu and Liu \cite{YL09} asked whether, for a given integer $k\geq 3$, every $k$-regular bipartite graph contains a 1-anti-factor. This paper answers this question in the affirmative.

---

The super-connectivity of Johnson graphs

Gülnaz Boruzanlı Ekinci ; John Baptist Gauci.

For positive integers $n,k$ and $t$, the uniform subset graph $G(n, k, t)$ has all $k$-subsets of $\{1,2,\ldots, n\}$ as vertices and two $k$-subsets are joined by an edge if they intersect at exactly $t$ elements. The Johnson graph $J(n,k)$ corresponds to $G(n,k,k-1)$, that is, two vertices of $J(n,k)$ are adjacent if the intersection of the corresponding $k$-subsets has size $k-1$. A super vertex-cut of a connected graph is a set of vertices whose removal disconnects the graph without isolating a vertex and the super-connectivity is the size of a minimum super vertex-cut. In this work, we fully determine the super-connectivity of the family of Johnson graphs $J(n,k)$ for $n\geq k\geq 1$.

---

The Chromatic Number of the Disjointness Graph of the Double Chain

Ruy Fabila-Monroy ; Carlos Hidalgo-Toscano ; Jesús Leaños ; Mario Lomelí-Haro.

Let $P$ be a set of $n\geq 4$ points in general position in the plane. Consider all the closed straight line segments with both endpoints in $P$. Suppose that these segments are colored with the rule that disjoint segments receive different colors. In this paper we show that if $P$ is the point configuration known as the double chain, with $k$ points in the upper convex chain and $l \ge k$ points in the lower convex chain, then $k+l- \left\lfloor \sqrt{2l+\frac{1}{4}} - \frac{1}{2}\right\rfloor$ colors are needed and that this number is sufficient.

---

A method for eternally dominating strong grids

Alizée Gagnon ; Alexander Hassler ; Jerry Huang ; Aaron Krim-Yee ; Fionn Mc Inerney ; Andrés Zacarías ; Ben Seamone ; Virgélot Virgile.

In the eternal domination game, an attacker attacks a vertex at each turn and a team of guards must move a guard to the attacked vertex to defend it. The guards may only move to adjacent vertices and no more than one guard may occupy a vertex. The goal is to determine the eternal domination number of a graph which is the minimum number of guards required to defend the graph against an infinite sequence of attacks. In this paper, we continue the study of the eternal domination game on strong grids. Cartesian grids have been vastly studied with tight bounds for small grids such as 2×n, 3×n, 4×n, and 5×n grids, and recently it was proven in [Lamprou et al., CIAC 2017, 393-404] that the eternal domination number of these grids in general is within O(m + n) of their domination number which lower bounds the eternal domination number. Recently, Finbow et al. proved that the eternal domination number of strong grids is upper bounded by mn 6 + O(m + n). We adapt the techniques of [Lamprou et al., CIAC 2017, 393-404] to prove that the eternal domination number of strong grids is upper bounded by mn 7 + O(m + n). While this does not improve upon a recently announced bound of ⎡m/3⎤ x⎡n/3⎤ + O(m √ n) [Mc Inerney, Nisse, Pérennes, HAL archives, 2018; Mc Inerney, Nisse, Pérennes, CIAC 2019] in the general case, we show that our bound is an improvement in the case where the smaller of the two dimensions is at most 6179.

---

On the Complexity of Digraph Colourings and Vertex Arboricity

Winfried Hochstättler ; Felix Schröder ; Raphael Steiner.

It has been shown by Bokal et al. that deciding 2-colourability of digraphs is an NP-complete problem. This result was later on extended by Feder et al. to prove that deciding whether a digraph has a circular $p$-colouring is NP-complete for all rational $p>1$. In this paper, we consider the complexity of corresponding decision problems for related notions of fractional colourings for digraphs and graphs, including the star dichromatic number, the fractional dichromatic number and the circular vertex arboricity. We prove the following results: Deciding if the star dichromatic number of a digraph is at most $p$ is NP-complete for every rational $p>1$. Deciding if the fractional dichromatic number of a digraph is at most $p$ is NP-complete for every $p>1, p \neq 2$. Deciding if the circular vertex arboricity of a graph is at most $p$ is NP-complete for every rational $p>1$. To show these results, different techniques are required in each case. In order to prove the first result, we relate the star dichromatic number to a new notion of homomorphisms between digraphs, called circular homomorphisms, which might be of independent interest. We provide a classification of the computational complexities of the corresponding homomorphism colouring problems similar to the one derived by Feder et al. for acyclic homomorphisms.

---

From light edges to strong edge-colouring of 1-planar graphs

Julien Bensmail ; François Dross ; Hervé Hocquard ; Eric Sopena.

A strong edge-colouring of an undirected graph $G$ is an edge-colouring where every two edges at distance at most~$2$ receive distinct colours. The strong chromatic index of $G$ is the least number of colours in a strong edge-colouring of $G$. A conjecture of Erdős and Nešet\v{r}il, stated back in the $80$'s, asserts that every graph with maximum degree $\Delta$ should have strong chromatic index at most roughly $1.25 \Delta^2$. Several works in the last decades have confirmed this conjecture for various graph classes. In particular, lots of attention have been dedicated to planar graphs, for which the strong chromatic index decreases to roughly $4\Delta$, and even to smaller values under additional structural requirements.In this work, we initiate the study of the strong chromatic index of $1$-planar graphs, which are those graphs that can be drawn on the plane in such a way that every edge is crossed at most once. We provide constructions of $1$-planar graphs with maximum degree~$\Delta$ and strong chromatic index roughly $6\Delta$. As an upper bound, we prove that the strong chromatic index of a $1$-planar graph with maximum degree $\Delta$ is at most roughly $24\Delta$ (thus linear in $\Delta$). The proof of this result is based on the existence of light edges in $1$-planar graphs with minimum degree at least~$3$.

---

Power domination in maximal planar graphs

Paul Dorbec ; Antonio González ; Claire Pennarun.

Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. It corresponds to a variant of domination that includes the possibility of propagation. For measurement devices placed on a set S of vertices of a graph G, the set of monitored vertices is initially the set S together with all its neighbors. Then iteratively, whenever some monitored vertex v has a single neighbor u not yet monitored, u gets monitored. A set S is said to be a power dominating set of the graph G if all vertices of G eventually are monitored. The power domination number of a graph is the minimum size of a power dominating set. In this paper, we prove that any maximal planar graph of order n ≥ 6 admits a power dominating set of size at most (n−2)/4 .

---

Generalized Petersen graphs and Kronecker covers

Matjaž Krnc ; Tomaž Pisanski.

The family of generalized Petersen graphs $G(n,k)$, introduced by Coxeter et al. [4] and named by Mark Watkins (1969), is a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. The Kronecker cover $KC(G)$ of a simple undirected graph $G$ is a a special type of bipartite covering graph of $G$, isomorphic to the direct (tensor) product of $G$ and $K_2$. We characterize all the members of generalized Petersen graphs that are Kronecker covers, and describe the structure of their respective quotients. We observe that some of such quotients are again generalized Petersen graphs, and describe all such pairs.The results of this paper have been presented at EUROCOMB 2019 and an extended abstract has been published elsewhere.

---

Equitable Coloring and Equitable Choosability of Planar Graphs without chordal 4- and 6-Cycles

Aijun Dong ; Jianliang Wu.

A graph $G$ is equitably $k$-choosable if, for any given $k$-uniform list assignment $L$, $G$ is $L$-colorable and each color appears on at most $\lceil\frac{|V(G)|}{k}\rceil$ vertices. A graph is equitably $k$-colorable if the vertex set $V(G)$ can be partitioned into $k$ independent subsets $V_1$, $V_2$, $\cdots$, $V_k$ such that $||V_i|-|V_j||\leq 1$ for $1\leq i, j\leq k$. In this paper, we prove that if $G$ is a planar graph without chordal $4$- and $6$-cycles, then $G$ is equitably $k$-colorable and equitably $k$-choosable where $k\geq\max\{\Delta(G), 7\}$.

---

Monochromatic loose paths in multicolored $k$-uniform cliques

Andrzej Dudek ; Andrzej Ruciński.

For integers $k\ge 2$ and $\ell\ge 0$, a $k$-uniform hypergraph is called a loose path of length $\ell$, and denoted by $P_\ell^{(k)}$, if it consists of $\ell $ edges $e_1,\dots,e_\ell$ such that $|e_i\cap e_j|=1$ if $|i-j|=1$ and $e_i\cap e_j=\emptyset$ if $|i-j|\ge2$. In other words, each pair of consecutive edges intersects on a single vertex, while all other pairs are disjoint. Let $R(P_\ell^{(k)};r)$ be the minimum integer $n$ such that every $r$-edge-coloring of the complete $k$-uniform hypergraph $K_n^{(k)}$ yields a monochromatic copy of $P_\ell^{(k)}$. In this paper we are mostly interested in constructive upper bounds on $R(P_\ell^{(k)};r)$, meaning that on the cost of possibly enlarging the order of the complete hypergraph, we would like to efficiently find a monochromatic copy of $P_\ell^{(k)}$ in every coloring. In particular, we show that there is a constant $c>0$ such that for all $k\ge 2$, $\ell\ge3$, $2\le r\le k-1$, and $n\ge k(\ell+1)r(1+\ln(r))$, there is an algorithm such that for every $r$-edge-coloring of the edges of $K_n^{(k)}$, it finds a monochromatic copy of $P_\ell^{(k)}$ in time at most $cn^k$. We also prove a non-constructive upper bound $R(P_\ell^{(k)};r)\le(k-1)\ell r$.

---

Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic

Kengo Enami.

Whitney's theorem states that every 3-connected planar graph is uniquely embeddable on the sphere. On the other hand, it has many inequivalent embeddings on another surface. We shall characterize structures of a $3$-connected $3$-regular planar graph $G$ embedded on the projective-plane, the torus and the Klein bottle, and give a one-to-one correspondence between inequivalent embeddings of $G$ on each surface and some subgraphs of the dual of $G$ embedded on the sphere. These results enable us to give explicit bounds for the number of inequivalent embeddings of $G$ on each surface, and propose effective algorithms for enumerating and counting these embeddings.

---

Constrained ear decompositions in graphs and digraphs

Frédéric Havet ; Nicolas Nisse.

Ear decompositions of graphs are a standard concept related to several major problems in graph theory like the Traveling Salesman Problem. For example, the Hamiltonian Cycle Problem, which is notoriously N P-complete, is equivalent to deciding whether a given graph admits an ear decomposition in which all ears except one are trivial (i.e. of length 1). On the other hand, a famous result of Lovász states that deciding whether a graph admits an ear decomposition with all ears of odd length can be done in polynomial time. In this paper, we study the complexity of deciding whether a graph admits an ear decomposition with prescribed ear lengths. We prove that deciding whether a graph admits an ear decomposition with all ears of length at most is polynomial-time solvable for all fixed positive integer. On the other hand, deciding whether a graph admits an ear decomposition without ears of length in F is N P-complete for any finite set F of positive integers. We also prove that, for any k ≥ 2, deciding whether a graph admits an ear decomposition with all ears of length 0 mod k is N P-complete. We also consider the directed analogue to ear decomposition, which we call handle decomposition, and prove analogous results : deciding whether a digraph admits a handle decomposition with all handles of length at most is polynomial-time solvable for all positive integer ; deciding whether a digraph admits a handle decomposition without handles of length in F is N P-complete for any finite […]

---

$(2/2/3)$-SAT problem and its applications in dominating set problems

Arash Ahadi ; Ali Dehghan.

The satisfiability problem is known to be $\mathbf{NP}$-complete in general and for many restricted cases. One way to restrict instances of $k$-SAT is to limit the number of times a variable can be occurred. It was shown that for an instance of 4-SAT with the property that every variable appears in exactly 4 clauses (2 times negated and 2 times not negated), determining whether there is an assignment for variables such that every clause contains exactly two true variables and two false variables is $\mathbf{NP}$-complete. In this work, we show that deciding the satisfiability of 3-SAT with the property that every variable appears in exactly four clauses (two times negated and two times not negated), and each clause contains at least two distinct variables is $ \mathbf{NP} $-complete. We call this problem $(2/2/3)$-SAT. For an $r$-regular graph $G = (V,E)$ with $r\geq 3$, it was asked in [Discrete Appl. Math., 160(15):2142--2146, 2012] to determine whether for a given independent set $T $ there is an independent dominating set $D$ that dominates $T$ such that $ T \cap D =\varnothing $? As an application of $(2/2/3)$-SAT problem we show that for every $r\geq 3$, this problem is $ \mathbf{NP} $-complete. Among other results, we study the relationship between 1-perfect codes and the incidence coloring of graphs and as another application of our complexity results, we prove that for a given cubic graph $G$ deciding whether $G$ is 4-incidence colorable is $ \mathbf{NP} $-complete.

---

On cordial labeling of hypertrees

Michał Tuczyński ; Przemysław Wenus ; Krzysztof Węsek.

Let $f:V\rightarrow\mathbb{Z}_k$ be a vertex labeling of a hypergraph $H=(V,E)$. This labeling induces an~edge labeling of $H$ defined by $f(e)=\sum_{v\in e}f(v)$, where the sum is taken modulo $k$. We say that $f$ is $k$-cordial if for all $a, b \in \mathbb{Z}_k$ the number of vertices with label $a$ differs by at most $1$ from the number of vertices with label $b$ and the analogous condition holds also for labels of edges. If $H$ admits a $k$-cordial labeling then $H$ is called $k$-cordial. The existence of $k$-cordial labelings has been investigated for graphs for decades. Hovey~(1991) conjectured that every tree $T$ is $k$-cordial for every $k\ge 2$. Cichacz, Görlich and Tuza~(2013) were first to investigate the analogous problem for hypertrees, that is, connected hypergraphs without cycles. The main results of their work are that every $k$-uniform hypertree is $k$-cordial for every $k\ge 2$ and that every hypertree with $n$ or $m$ odd is $2$-cordial. Moreover, they conjectured that in fact all hypertrees are $2$-cordial. In this article, we confirm the conjecture of Cichacz et al. and make a step further by proving that for $k\in\{2,3\}$ every hypertree is $k$-cordial.

---

Super edge-connectivity and matching preclusion of data center networks

Huazhong Lü ; Tingzeng Wu.

Edge-connectivity is a classic measure for reliability of a network in the presence of edge failures. $k$-restricted edge-connectivity is one of the refined indicators for fault tolerance of large networks. Matching preclusion and conditional matching preclusion are two important measures for the robustness of networks in edge fault scenario. In this paper, we show that the DCell network $D_{k,n}$ is super-$\lambda$ for $k\geq2$ and $n\geq2$, super-$\lambda_2$ for $k\geq3$ and $n\geq2$, or $k=2$ and $n=2$, and super-$\lambda_3$ for $k\geq4$ and $n\geq3$. Moreover, as an application of $k$-restricted edge-connectivity, we study the matching preclusion number and conditional matching preclusion number, and characterize the corresponding optimal solutions of $D_{k,n}$. In particular, we have shown that $D_{1,n}$ is isomorphic to the $(n,k)$-star graph $S_{n+1,2}$ for $n\geq2$.

---

Extremal properties of flood-filling games

Kitty Meeks ; Dominik K. Vu.

The problem of determining the number of "flooding operations" required to make a given coloured graph monochromatic in the one-player combinatorial game Flood-It has been studied extensively from an algorithmic point of view, but basic questions about the maximum number of moves that might be required in the worst case remain unanswered. We begin a systematic investigation of such questions, with the goal of determining, for a given graph, the maximum number of moves that may be required, taken over all possible colourings. We give several upper and lower bounds on this quantity for arbitrary graphs and show that all of the bounds are tight for trees; we also investigate how much the upper bounds can be improved if we restrict our attention to graphs with higher edge-density.

---

On almost hypohamiltonian graphs

Jan Goedgebeur ; Carol T. Zamfirescu.

A graph $G$ is almost hypohamiltonian (a.h.) if $G$ is non-hamiltonian, there exists a vertex $w$ in $G$ such that $G - w$ is non-hamiltonian, and $G - v$ is hamiltonian for every vertex $v \ne w$ in $G$. The second author asked in [J. Graph Theory 79 (2015) 63--81] for all orders for which a.h. graphs exist. Here we solve this problem. To this end, we present a specialised algorithm which generates complete sets of a.h. graphs for various orders. Furthermore, we show that the smallest cubic a.h. graphs have order 26. We provide a lower bound for the order of the smallest planar a.h. graph and improve the upper bound for the order of the smallest planar a.h. graph containing a cubic vertex. We also determine the smallest planar a.h. graphs of girth 5, both in the general and cubic case. Finally, we extend a result of Steffen on snarks and improve two bounds on longest paths and longest cycles in polyhedral graphs due to Jooyandeh, McKay, {\"O}sterg{\aa}rd, Pettersson, and the second author.

---

A note on the convexity number for complementary prisms

Diane Castonguay ; Erika M. M. Coelho ; Hebert Coelho ; Julliano R. Nascimento.

In the geodetic convexity, a set of vertices $S$ of a graph $G$ is $\textit{convex}$ if all vertices belonging to any shortest path between two vertices of $S$ lie in $S$. The cardinality $con(G)$ of a maximum proper convex set $S$ of $G$ is the $\textit{convexity number}$ of $G$. The $\textit{complementary prism}$ $G\overline{G}$ of a graph $G$ arises from the disjoint union of the graph $G$ and $\overline{G}$ by adding the edges of a perfect matching between the corresponding vertices of $G$ and $\overline{G}$. In this work, we we prove that the decision problem related to the convexity number is NP-complete even restricted to complementary prisms, we determine $con(G\overline{G})$ when $G$ is disconnected or $G$ is a cograph, and we present a lower bound when $diam(G) \neq 3$.

---

Backbone colouring and algorithms for TDMA scheduling

Julien Bensmail ; Thibaut Blanc ; Nathann Cohen ; Frédéric Havet ; Leonardo Rocha.

We investigate graph colouring models for the purpose of optimizing TDMA link scheduling in Wireless Networks. Inspired by the BPRN-colouring model recently introduced by Rocha and Sasaki, we introduce a new colouring model, namely the BMRN-colouring model, which can be used to model link scheduling problems where particular types of collisions must be avoided during the node transmissions. In this paper, we initiate the study of the BMRN-colouring model by providing several bounds on the minimum number of colours needed to BMRN-colour digraphs, as well as several complexity results establishing the hardness of finding optimal colourings. We also give a special focus on these considerations for planar digraph topologies, for which we provide refined results.

---

On the multipacking number of grid graphs

Laurent Beaudou ; Richard C. Brewster.

In 2001, Erwin introduced broadcast domination in graphs. It is a variant of classical domination where selected vertices may have different domination powers. The minimum cost of a dominating broadcast in a graph $G$ is denoted $\gamma_b(G)$. The dual of this problem is called multipacking: a multipacking is a set $M$ of vertices such that for any vertex $v$ and any positive integer $r$, the ball of radius $r$ around $v$ contains at most $r$ vertices of $M$ . The maximum size of a multipacking in a graph $G$ is denoted mp(G). Naturally mp(G) $\leq \gamma_b(G)$. Earlier results by Farber and by Lubiw show that broadcast and multipacking numbers are equal for strongly chordal graphs. In this paper, we show that all large grids (height at least 4 and width at least 7), which are far from being chordal, have their broadcast and multipacking numbers equal.

---

The agreement distance of rooted phylogenetic networks

Jonathan Klawitter.

The minimal number of rooted subtree prune and regraft (rSPR) operations needed to transform one phylogenetic tree into another one induces a metric on phylogenetic trees - the rSPR-distance. The rSPR-distance between two phylogenetic trees $T$ and $T'$ can be characterised by a maximum agreement forest; a forest with a minimum number of components that covers both $T$ and $T'$. The rSPR operation has recently been generalised to phylogenetic networks with, among others, the subnetwork prune and regraft (SNPR) operation. Here, we introduce maximum agreement graphs as an explicit representations of differences of two phylogenetic networks, thus generalising maximum agreement forests. We show that maximum agreement graphs induce a metric on phylogenetic networks - the agreement distance. While this metric does not characterise the distances induced by SNPR and other generalisations of rSPR, we prove that it still bounds these distances with constant factors.

---

Exact values for three domination-like problems in circular and infinite grid graphs of small height

Marwane Bouznif ; Julien Darlay ; Julien Moncel ; Myriam Preissmann.

In this paper we study three domination-like problems, namely identifying codes, locating-dominating codes, and locating-total-dominating codes. We are interested in finding the minimum cardinality of such codes in circular and infinite grid graphs of given height. We provide an alternate proof for already known results, as well as new results. These were obtained by a computer search based on a generic framework, that we developed earlier, for the search of a minimum labeling satisfying a pseudo-d-local property in rotagraphs.

---

Some results on the palette index of graphs

C. J. Casselgren ; Petros A. Petrosyan.

Given a proper edge coloring $\varphi$ of a graph $G$, we define the palette $S_{G}(v,\varphi)$ of a vertex $v \in V(G)$ as the set of all colors appearing on edges incident with $v$. The palette index $\check s(G)$ of $G$ is the minimum number of distinct palettes occurring in a proper edge coloring of $G$. In this paper we give various upper and lower bounds on the palette index of $G$ in terms of the vertex degrees of $G$, particularly for the case when $G$ is a bipartite graph with small vertex degrees. Some of our results concern $(a,b)$-biregular graphs; that is, bipartite graphs where all vertices in one part have degree $a$ and all vertices in the other part have degree $b$. We conjecture that if $G$ is $(a,b)$-biregular, then $\check{s}(G)\leq 1+\max\{a,b\}$, and we prove that this conjecture holds for several families of $(a,b)$-biregular graphs. Additionally, we characterize the graphs whose palette index equals the number of vertices.

---

Bounds for the smallest $k$-chromatic graphs of given girth

Geoffrey Exoo ; Jan Goedgebeur.

Let $n_g(k)$ denote the smallest order of a $k$-chromatic graph of girth at least $g$. We consider the problem of determining $n_g(k)$ for small values of $k$ and $g$. After giving an overview of what is known about $n_g(k)$, we provide some new lower bounds based on exhaustive searches, and then obtain several new upper bounds using computer algorithms for the construction of witnesses, and for the verification of their correctness. We also present the first examples of reasonably small order for $k = 4$ and $g > 5$. In particular, the new bounds include: $n_4(7) \leq 77$, $26 \leq n_6(4) \leq 66$, $30 \leq n_7(4) \leq 171$.

---

Slimness of graphs

Feodor F. Dragan ; Abdulhakeem Mohammed.

Slimness of a graph measures the local deviation of its metric from a tree metric. In a graph $G=(V,E)$, a geodesic triangle $\bigtriangleup(x,y,z)$ with $x, y, z\in V$ is the union $P(x,y) \cup P(x,z) \cup P(y,z)$ of three shortest paths connecting these vertices. A geodesic triangle $\bigtriangleup(x,y,z)$ is called $\delta$-slim if for any vertex $u\in V$ on any side $P(x,y)$ the distance from $u$ to $P(x,z) \cup P(y,z)$ is at most $\delta$, i.e. each path is contained in the union of the $\delta$-neighborhoods of two others. A graph $G$ is called $\delta$-slim, if all geodesic triangles in $G$ are $\delta$-slim. The smallest value $\delta$ for which $G$ is $\delta$-slim is called the slimness of $G$. In this paper, using the layering partition technique, we obtain sharp bounds on slimness of such families of graphs as (1) graphs with cluster-diameter $\Delta(G)$ of a layering partition of $G$, (2) graphs with tree-length $\lambda$, (3) graphs with tree-breadth $\rho$, (4) $k$-chordal graphs, AT-free graphs and HHD-free graphs. Additionally, we show that the slimness of every 4-chordal graph is at most 2 and characterize those 4-chordal graphs for which the slimness of every of its induced subgraph is at most 1.

---

Packing chromatic vertex-critical graphs

Sandi Klavžar ; Douglas F. Rall.

The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $k$ such that the vertex set of $G$ can be partitioned into sets $V_i$, $i\in [k]$, where vertices in $V_i$ are pairwise at distance at least $i+1$. Packing chromatic vertex-critical graphs, $\chi_{\rho}$-critical for short, are introduced as the graphs $G$ for which $\chi_{\rho}(G-x) < \chi_{\rho}(G)$ holds for every vertex $x$ of $G$. If $\chi_{\rho}(G) = k$, then $G$ is $k$-$\chi_{\rho}$-critical. It is shown that if $G$ is $\chi_{\rho}$-critical, then the set $\{\chi_{\rho}(G) - \chi_{\rho}(G-x):\ x\in V(G)\}$ can be almost arbitrary. The $3$-$\chi_{\rho}$-critical graphs are characterized, and $4$-$\chi_{\rho}$-critical graphs are characterized in the case when they contain a cycle of length at least $5$ which is not congruent to $0$ modulo $4$. It is shown that for every integer $k\ge 2$ there exists a $k$-$\chi_{\rho}$-critical tree and that a $k$-$\chi_{\rho}$-critical caterpillar exists if and only if $k\le 7$. Cartesian products are also considered and in particular it is proved that if $G$ and $H$ are vertex-transitive graphs and ${\rm diam(G)} + {\rm diam}(H) \le \chi_{\rho}(G)$, then $G\,\square\, H$ is $\chi_{\rho}$-critical.

---

Packing coloring of generalized Sierpinski graphs

Danilo Korze ; Aleksander Vesel.

The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $c$ such that the vertex set $V(G)$ can be partitioned into sets $X_1, . . . , X_c$, with the condition that vertices in $X_i$ have pairwise distance greater than $i$. In this paper, we consider the packing chromatic number of several families of Sierpinski-type graphs. We establish the packing chromatic numbers of generalized Sierpinski graphs $S^n_G$ where $G$ is a path or a cycle (with exception of a cycle of length five) as well as a connected graph of order four. Furthermore, we prove that the packing chromatic number in the family of Sierpinski-triangle graphs $ST_4^n$ is bounded from above by 20.

---

On the maximum number of minimum total dominating sets in forests

Michael A. Henning ; Elena Mohr ; Dieter Rautenbach.

We propose the conjecture that every tree with order $n$ at least $2$ and total domination number $\gamma_t$ has at most $\left(\frac{n-\frac{\gamma_t}{2}}{\frac{\gamma_t}{2}}\right)^{\frac{\gamma_t}{2}}$ minimum total dominating sets. As a relaxation of this conjecture, we show that every forest $F$ with order $n$, no isolated vertex, and total domination number $\gamma_t$ has at most $\min\left\{\left(8\sqrt{e}\, \right)^{\gamma_t}\left(\frac{n-\frac{\gamma_t}{2}}{\frac{\gamma_t}{2}}\right)^{\frac{\gamma_t}{2}}, (1+\sqrt{2})^{n-\gamma_t},1.4865^n\right\}$ minimum total dominating sets.

---

Binding Number, Toughness and General Matching Extendability in Graphs

Hongliang Lu ; Qinglin Yu.

A connected graph $G$ with at least $2m + 2n + 2$ vertices which contains a perfect matching is $E(m, n)$-{\it extendable}, if for any two sets of disjoint independent edges $M$ and $N$ with $|M| = m$ and $|N|= n$, there is a perfect matching $F$ in $G$ such that $M\subseteq F$ and $N\cap F=\emptyset$. Similarly, a connected graph with at least $n+2k+2$ vertices is called $(n,k)$-{\it extendable} if for any vertex set $S$ of size $n$ and any matching $M$ of size $k$ of $G-S$, $G-S-V(M)$ contains a perfect matching. Let $\varepsilon$ be a small positive constant, $b(G)$ and $t(G)$ be the binding number and toughness of a graph $G$. The two main theorems of this paper are: for every graph $G$ with sufficiently large order, 1) if $b(G)\geq 4/3+\varepsilon$, then $G$ is $E(m,n)$-extendable and also $(n,k)$-extendable; 2) if $t(G)\geq 1+\varepsilon$ and $G$ has a high connectivity, then $G$ is $E(m,n)$-extendable and also $(n,k)$-extendable. It is worth to point out that the binding number and toughness conditions for the existence of the general matching extension properties are almost same as that for the existence of perfect matchings.

---

Solving Two Conjectures regarding Codes for Location in Circulant Graphs

Ville Junnila ; Tero Laihonen ; Gabrielle Paris.

Identifying and locating-dominating codes have been widely studied in circulant graphs of type $C_n(1,2, \ldots, r)$, which can also be viewed as power graphs of cycles. Recently, Ghebleh and Niepel (2013) considered identification and location-domination in the circulant graphs $C_n(1,3)$. They showed that the smallest cardinality of a locating-dominating code in $C_n(1,3)$ is at least $\lceil n/3 \rceil$ and at most $\lceil n/3 \rceil + 1$ for all $n \geq 9$. Moreover, they proved that the lower bound is strict when $n \equiv 0, 1, 4 \pmod{6}$ and conjectured that the lower bound can be increased by one for other $n$. In this paper, we prove their conjecture. Similarly, they showed that the smallest cardinality of an identifying code in $C_n(1,3)$ is at least $\lceil 4n/11 \rceil$ and at most $\lceil 4n/11 \rceil + 1$ for all $n \geq 11$. Furthermore, they proved that the lower bound is attained for most of the lengths $n$ and conjectured that in the rest of the cases the lower bound can improved by one. This conjecture is also proved in the paper. The proofs of the conjectures are based on a novel approach which, instead of making use of the local properties of the graphs as is usual to identification and location-domination, also manages to take advantage of the global properties of the codes and the underlying graphs.

---

Sigma Partitioning: Complexity and Random Graphs

Ali Dehghan ; Mohammad-Reza Sadeghi ; Arash Ahadi.

A $\textit{sigma partitioning}$ of a graph $G$ is a partition of the vertices into sets $P_1, \ldots, P_k$ such that for every two adjacent vertices $u$ and $v$ there is an index $i$ such that $u$ and $v$ have different numbers of neighbors in $P_i$. The $\textit{ sigma number}$ of a graph $G$, denoted by $\sigma(G)$, is the minimum number $k$ such that $ G $ has a sigma partitioning $P_1, \ldots, P_k$. Also, a $\textit{ lucky labeling}$ of a graph $G$ is a function $ \ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent vertices $ v $ and $ u$ of $ G $, $ \sum_{w \sim v}\ell(w)\neq \sum_{w \sim u}\ell(w) $ ($ x \sim y $ means that $ x $ and $y$ are adjacent). The $\textit{ lucky number}$ of $ G $, denoted by $\eta(G)$, is the minimum number $k $ such that $ G $ has a lucky labeling $ \ell :V(G) \rightarrow \mathbb{N}_k$. It was conjectured in [Inform. Process. Lett., 112(4):109--112, 2012] that it is $ \mathbf{NP} $-complete to decide whether $ \eta(G)=2$ for a given 3-regular graph $G$. In this work, we prove this conjecture. Among other results, we give an upper bound of five for the sigma number of a uniformly random graph.

---

Solving the kernel perfect problem by (simple) forbidden subdigraphs for digraphs in some families of generalized tournaments and generalized bipartite tournaments

H. Galeana-Sánchez ; M. Olsen.

A digraph such that every proper induced subdigraph has a kernel is said to be \emph{kernel perfect} (KP for short) (\emph{critical kernel imperfect} (CKI for short) resp.) if the digraph has a kernel (does not have a kernel resp.). The unique CKI-tournament is $\overrightarrow{C}_3$ and the unique KP-tournaments are the transitive tournaments, however bipartite tournaments are KP. In this paper we characterize the CKI- and KP-digraphs for the following families of digraphs: locally in-/out-semicomplete, asymmetric arc-locally in-/out-semicomplete, asymmetric $3$-quasi-transitive and asymmetric $3$-anti-quasi-transitive $TT_3$-free and we state that the problem of determining whether a digraph of one of these families is CKI is polynomial, giving a solution to a problem closely related to the following conjecture posted by Bang-Jensen in 1998: the kernel problem is polynomially solvable for locally in-semicomplete digraphs.

---

Complexity of locally-injective homomorphisms to tournaments

Stefan Bard ; Thomas Bellitto ; Christopher Duffy ; Gary MacGillivray ; Feiran Yang.

For oriented graphs $G$ and $H$, a homomorphism $f: G \rightarrow H$ is locally-injective if, for every $v \in V(G)$, it is injective when restricted to some combination of the in-neighbourhood and out-neighbourhood of $v$. Two of the possible definitions of local-injectivity are examined. In each case it is shown that the associated homomorphism problem is NP-complete when $H$ is a reflexive tournament on three or more vertices with a loop at every vertex, and solvable in polynomial time when $H$ is a reflexive tournament on two or fewer vertices.

---

Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs

Fábio Protti ; Uéverton S. Souza.

A graph $G$ is {\em matching-decyclable} if it has a matching $M$ such that $G-M$ is acyclic. Deciding whether $G$ is matching-decyclable is an NP-complete problem even if $G$ is 2-connected, planar, and subcubic. In this work we present results on matching-decyclability in the following classes: Hamiltonian subcubic graphs, chordal graphs, and distance-hereditary graphs. In Hamiltonian subcubic graphs we show that deciding matching-decyclability is NP-complete even if there are exactly two vertices of degree two. For chordal and distance-hereditary graphs, we present characterizations of matching-decyclability that lead to $O(n)$-time recognition algorithms.

---

On Almost Well-Covered Graphs of Girth at Least 6

Tınaz Ekim ; Didem Gözüpek ; Ademir Hujdurović ; Martin Milanič.

We consider a relaxation of the concept of well-covered graphs, which are graphs with all maximal independent sets of the same size. The extent to which a graph fails to be well-covered can be measured by its independence gap, defined as the difference between the maximum and minimum sizes of a maximal independent set in $G$. While the well-covered graphs are exactly the graphs of independence gap zero, we investigate in this paper graphs of independence gap one, which we also call almost well-covered graphs. Previous works due to Finbow et al. (1994) and Barbosa et al. (2013) have implications for the structure of almost well-covered graphs of girth at least $k$ for $k\in \{7,8\}$. We focus on almost well-covered graphs of girth at least $6$. We show that every graph in this class has at most two vertices each of which is adjacent to exactly $2$ leaves. We give efficiently testable characterizations of almost well-covered graphs of girth at least $6$ having exactly one or exactly two such vertices. Building on these results, we develop a polynomial-time recognition algorithm of almost well-covered $\{C_3,C_4,C_5,C_7\}$-free graphs.

---

General bounds on limited broadcast domination

José Cáceres ; Carmen Hernando ; Mercè Mora ; Ignacio M. Pelayo ; María Luz Puertas.

Dominating broadcasting is a domination-type structure that models a transmission antenna network. In this paper, we study a limited version of this structure, that was proposed as a common framework for both broadcast and classical domination. In this limited version, the broadcast function is upper bounded by an integer $k$ and the minimum cost of such function is the dominating $k$-broadcast number. Our main result is a unified upper bound on this parameter for any value of $k$ in general graphs, in terms of both $k$ and the order of the graph. We also study the computational complexity of the associated decision problem.

---

Steiner Distance in Product Networks

Yaping Mao ; Eddie Cheng ; Zhao Wang.

For a connected graph $G$ of order at least $2$ and $S\subseteq V(G)$, the \emph{Steiner distance} $d_G(S)$ among the vertices of $S$ is the minimum size among all connected subgraphs whose vertex sets contain $S$. Let $n$ and $k$ be two integers with $2\leq k\leq n$. Then the \emph{Steiner $k$-eccentricity $e_k(v)$} of a vertex $v$ of $G$ is defined by $e_k(v)=\max \{d_G(S)\,|\,S\subseteq V(G), \ |S|=k, \ and \ v\in S\}$. Furthermore, the \emph{Steiner $k$-diameter} of $G$ is $sdiam_k(G)=\max \{e_k(v)\,|\, v\in V(G)\}$. In this paper, we investigate the Steiner distance and Steiner $k$-diameter of Cartesian and lexicographical product graphs. Also, we study the Steiner $k$-diameter of some networks.

---

Fast strategies in biased Maker--Breaker games

Mirjana Mikalački ; Miloš Stojaković.

We study the biased $(1:b)$ Maker--Breaker positional games, played on the edge set of the complete graph on $n$ vertices, $K_n$. Given Breaker's bias $b$, possibly depending on $n$, we determine the bounds for the minimal number of moves, depending on $b$, in which Maker can win in each of the two standard graph games, the Perfect Matching game and the Hamilton Cycle game.

---

On locally irregular decompositions and the 1-2 Conjecture in digraphs

Olivier Baudon ; Julien Bensmail ; Jakub Przybyło ; Mariusz Woźniak.

The 1-2 Conjecture raised by Przybylo and Wozniak in 2010 asserts that every undirected graph admits a 2-total-weighting such that the sums of weights "incident" to the vertices yield a proper vertex-colouring. Following several recent works bringing related problems and notions (such as the well-known 1-2-3 Conjecture, and the notion of locally irregular decompositions) to digraphs, we here introduce and study several variants of the 1-2 Conjecture for digraphs. For every such variant, we raise conjectures concerning the number of weights necessary to obtain a desired total-weighting in any digraph. We verify some of these conjectures, while we obtain close results towards the ones that are still open.

---

Semitotal domination in trees

Zhuang Wei ; Hao Guoliang.

In this paper, we study a parameter that is squeezed between arguably the two important domination parameters, namely the domination number, $\gamma(G)$, and the total domination number, $\gamma_t(G)$. A set $S$ of vertices in $G$ is a semitotal dominating set of $G$ if it is a dominating set of $G$ and every vertex in S is within distance $2$ of another vertex of $S$. The semitotal domination number, $\gamma_{t2}(G)$, is the minimum cardinality of a semitotal dominating set of $G$. We observe that $\gamma(G)\leq \gamma_{t2}(G)\leq \gamma_t(G)$. In this paper, we give a lower bound for the semitotal domination number of trees and we characterize the extremal trees. In addition, we characterize trees with equal domination and semitotal domination numbers.

---

On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width

M. Rajaati ; M. R. Hooshmandasl ; M. J. Dinneen ; A. Shakiba.

A mixed dominating set for a graph $G = (V,E)$ is a set $S\subseteq V \cup E$ such that every element $x \in (V \cup E) \backslash S$ is either adjacent or incident to an element of $S$. The mixed domination number of a graph $G$, denoted by $\gamma_m(G)$, is the minimum cardinality of mixed dominating sets of $G$. Any mixed dominating set with the cardinality of $\gamma_m(G)$ is called a minimum mixed dominating set. The mixed domination set (MDS) problem is to find a minimum mixed dominating set for a graph $G$ and is known to be an NP-complete problem. In this paper, we present a novel approach to find all of the mixed dominating sets, called the AMDS problem, of a graph with bounded tree-width $tw$. Our new technique of assigning power values to edges and vertices, and combining with dynamic programming, leads to a fixed-parameter algorithm of time $O(3^{tw^{2}}\times tw^2 \times |V|)$. This shows that MDS is fixed-parameter tractable with respect to tree-width. In addition, we theoretically improve the proposed algorithm to solve the MDS problem in $O(6^{tw} \times |V|)$ time.

---

Group twin coloring of graphs

Sylwia Cichacz ; Jakub Przybyło.

For a given graph $G$, the least integer $k\geq 2$ such that for every Abelian group $\mathcal{G}$ of order $k$ there exists a proper edge labeling $f:E(G)\rightarrow \mathcal{G}$ so that $\sum_{x\in N(u)}f(xu)\neq \sum_{x\in N(v)}f(xv)$ for each edge $uv\in E(G)$ is called the \textit{group twin chromatic index} of $G$ and denoted by $\chi'_g(G)$. This graph invariant is related to a few well-known problems in the field of neighbor distinguishing graph colorings. We conjecture that $\chi'_g(G)\leq \Delta(G)+3$ for all graphs without isolated edges, where $\Delta(G)$ is the maximum degree of $G$, and provide an infinite family of connected graph (trees) for which the equality holds. We prove that this conjecture is valid for all trees, and then apply this result as the base case for proving a general upper bound for all graphs $G$ without isolated edges: $\chi'_g(G)\leq 2(\Delta(G)+{\rm col}(G))-5$, where ${\rm col}(G)$ denotes the coloring number of $G$. This improves the best known upper bound known previously only for the case of cyclic groups $\mathbb{Z}_k$.

---

A Sufficient Condition for Graphic Sequences with Given Largest and Smallest Entries, Length, and Sum

Brian Cloteaux.

We give a sufficient condition for a degree sequence to be graphic based on its largest and smallest elements, length, and sum. This bound generalizes a result of Zverovich and Zverovich.

---

On a Class of Graphs with Large Total Domination Number

Selim Bahadır ; Didem Gözüpek.

Let $\gamma(G)$ and $\gamma_t(G)$ denote the domination number and the total domination number, respectively, of a graph $G$ with no isolated vertices. It is well-known that $\gamma_t(G) \leq 2\gamma(G)$. We provide a characterization of a large family of graphs (including chordal graphs) satisfying $\gamma_t(G)= 2\gamma(G)$, strictly generalizing the results of Henning (2001) and Hou et al. (2010), and partially answering an open question of Henning (2009).

---

Computing Minimum Rainbow and Strong Rainbow Colorings of Block Graphs

Melissa Keranen ; Juho Lauri.

A path in an edge-colored graph $G$ is rainbow if no two edges of it are colored the same. The graph $G$ is rainbow-connected if there is a rainbow path between every pair of vertices. If there is a rainbow shortest path between every pair of vertices, the graph $G$ is strongly rainbow-connected. The minimum number of colors needed to make $G$ rainbow-connected is known as the rainbow connection number of $G$, and is denoted by $\text{rc}(G)$. Similarly, the minimum number of colors needed to make $G$ strongly rainbow-connected is known as the strong rainbow connection number of $G$, and is denoted by $\text{src}(G)$. We prove that for every $k \geq 3$, deciding whether $\text{src}(G) \leq k$ is NP-complete for split graphs, which form a subclass of chordal graphs. Furthermore, there exists no polynomial-time algorithm for approximating the strong rainbow connection number of an $n$-vertex split graph with a factor of $n^{1/2-\epsilon}$ for any $\epsilon > 0$ unless P = NP. We then turn our attention to block graphs, which also form a subclass of chordal graphs. We determine the strong rainbow connection number of block graphs, and show it can be computed in linear time. Finally, we provide a polynomial-time characterization of bridgeless block graphs with rainbow connection number at most 4.

---

On neighbour sum-distinguishing $\{0,1\}$-edge-weightings of bipartite graphs

Kasper Szabo Lyngsie.

Let $S$ be a set of integers. A graph G is said to have the S-property if there exists an S-edge-weighting $w : E(G) \rightarrow S$ such that any two adjacent vertices have different sums of incident edge-weights. In this paper we characterise all bridgeless bipartite graphs and all trees without the $\{0,1\}$-property. In particular this problem belongs to P for these graphs while it is NP-complete for all graphs.

---

Forbidden subgraphs for constant domination number

Michitaka Furuya.

In this paper, we characterize the sets $\mathcal{H}$ of connected graphs such that there exists a constant $c=c(\mathcal{H})$ satisfying $\gamma (G)\leq c$ for every connected $\mathcal{H}$-free graph $G$, where $\gamma (G)$ is the domination number of $G$.

---

Proof of a local antimagic conjecture

John Haslegrave.

An antimagic labelling of a graph $G$ is a bijection $f:E(G)\to\{1,\ldots,E(G)\}$ such that the sums $S_v=\sum_{e\ni v}f(e)$ distinguish all vertices. A well-known conjecture of Hartsfield and Ringel (1994) is that every connected graph other than $K_2$ admits an antimagic labelling. Recently, two sets of authors (Arumugam, Premalatha, Ba\v{c}a \& Semani\v{c}ová-Fe\v{n}ov\v{c}\'iková (2017), and Bensmail, Senhaji \& Lyngsie (2017)) independently introduced the weaker notion of a local antimagic labelling, where only adjacent vertices must be distinguished. Both sets of authors conjectured that any connected graph other than $K_2$ admits a local antimagic labelling. We prove this latter conjecture using the probabilistic method. Thus the parameter of local antimagic chromatic number, introduced by Arumugam et al., is well-defined for every connected graph other than $K_2$ .

---

Weakly threshold graphs

Michael D. Barrus.

We define a weakly threshold sequence to be a degree sequence $d=(d_1,\dots,d_n)$ of a graph having the property that $\sum_{i \leq k} d_i \geq k(k-1)+\sum_{i > k} \min\{k,d_i\} - 1$ for all positive $k \leq \max\{i:d_i \geq i-1\}$. The weakly threshold graphs are the realizations of the weakly threshold sequences. The weakly threshold graphs properly include the threshold graphs and satisfy pleasing extensions of many properties of threshold graphs. We demonstrate a majorization property of weakly threshold sequences and an iterative construction algorithm for weakly threshold graphs, as well as a forbidden induced subgraph characterization. We conclude by exactly enumerating weakly threshold sequences and graphs.

---

Annular and pants thrackles

Grace Misereh ; Yuri Nikolayevsky.

A thrackle is a drawing of a graph in which each pair of edges meets precisely once. Conway's Thrackle Conjecture asserts that a thrackle drawing of a graph on the plane cannot have more edges than vertices. We prove the Conjecture for thrackle drawings all of whose vertices lie on the boundaries of $d \le 3$ connected domains in the complement of the drawing. We also give a detailed description of thrackle drawings corresponding to the cases when $d=2$ (annular thrackles) and $d=3$ (pants thrackles).

---

On interval number in cycle convexity

Julio Araujo ; Guillaume Ducoffe ; Nicolas Nisse ; Karol Suchan.

Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by $in_{cc} (G)$, is the minimum cardinality of a set S ⊆ V (G) such that every vertex w ∈ V (G) \ S has two distinct neighbors u, v ∈ S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S.In this work, first we provide bounds on $in_{cc} (G)$ and its relations to other graph convexity parameters, and explore its behavior on grids. Then, we present some hardness results by showing that deciding whether $in_{cc} (G)$ ≤ k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtainthat $in_{cc} (G)$ cannot be […]

---

Finding Hamilton cycles in random intersection graphs

Katarzyna Rybarczyk.

The construction of the random intersection graph model is based on a random family of sets. Such structures, which are derived from intersections of sets, appear in a natural manner in many applications. In this article we study the problem of finding a Hamilton cycle in a random intersection graph. To this end we analyse a classical algorithm for finding Hamilton cycles in random graphs (algorithm HAM) and study its efficiency on graphs from a family of random intersection graphs (denoted here by G(n,m,p)). We prove that the threshold function for the property of HAM constructing a Hamilton cycle in G(n,m,p) is the same as the threshold function for the minimum degree at least two. Until now, known algorithms for finding Hamilton cycles in G(n,m,p) were designed to work in very small ranges of parameters and, unlike HAM, used the structure of the family of random sets.

---

A Study of $k$-dipath Colourings of Oriented Graphs

Christopher Duffy ; Gary MacGillivray ; Éric Sopena.

We examine $t$-colourings of oriented graphs in which, for a fixed integer $k \geq 1$, vertices joined by a directed path of length at most $k$ must be assigned different colours. A homomorphism model that extends the ideas of Sherk for the case $k=2$ is described. Dichotomy theorems for the complexity of the problem of deciding, for fixed $k$ and $t$, whether there exists such a $t$-colouring are proved.

---

Weak embeddings of posets to the Boolean lattice

Dömötör Pálvölgyi.

The goal of this paper is to prove that several variants of deciding whether a poset can be (weakly) embedded into a small Boolean lattice, or to a few consecutive levels of a Boolean lattice, are NP-complete, answering a question of Griggs and of Patkos. As an equivalent reformulation of one of these problems, we also derive that it is NP-complete to decide whether a given graph can be embedded to the two middle levels of some hypercube.

---

Hitting minors, subdivisions, and immersions in tournaments

Jean-Florent Raymond.

The Erdős-Pósa property relates parameters of covering and packing of combinatorial structures and has been mostly studied in the setting of undirected graphs. In this note, we use results of Chudnovsky, Fradkin, Kim, and Seymour to show that, for every directed graph $H$ (resp. strongly-connected directed graph $H$), the class of directed graphs that contain $H$ as a strong minor (resp. butterfly minor, topological minor) has the vertex-Erdős-Pósa property in the class of tournaments. We also prove that if $H$ is a strongly-connected directed graph, the class of directed graphs containing $H$ as an immersion has the edge-Erdős-Pósa property in the class of tournaments.

---

A Variation on Chip-Firing: the diffusion game

C. Duffy ; T. F. Lidbetter ; M. E. Messinger ; R. J. Nowakowski.

We introduce a natural variant of the parallel chip-firing game, called the diffusion game. Chips are initially assigned to vertices of a graph. At every step, all vertices simultaneously send one chip to each neighbour with fewer chips. As the dynamics of the parallel chip-firing game occur on a finite set the process is inherently periodic. However the diffusion game is not obviously periodic: even if $2|E(G)|$ chips are assigned to vertices of graph G, there may exist time steps where some vertices have a negative number of chips. We investigate the process, prove periodicity for a number of graph classes, and pose some questions for future research.

---

Three matching intersection property for matching covered graphs

Hao Lin ; Xiumei Wang.

In connection with Fulkerson's conjecture on cycle covers, Fan and Raspaud proposed a weaker conjecture: For every bridgeless cubic graph $G$, there are three perfect matchings $M_1$, $M_2$, and $M_3$ such that $M_1\cap M_2 \cap M_3=\emptyset$. We call the property specified in this conjecture the three matching intersection property (and 3PM property for short). We study this property on matching covered graphs. The main results are a necessary and sufficient condition and its applications to characterization of special graphs, such as the Halin graphs and 4-regular graphs.

---

On Minimum Maximal Distance-k Matchings

Yury Kartynnik ; Andrew Ryzhikov.

We study the computational complexity of several problems connected with finding a maximal distance-$k$ matching of minimum cardinality or minimum weight in a given graph. We introduce the class of $k$-equimatchable graphs which is an edge analogue of $k$-equipackable graphs. We prove that the recognition of $k$-equimatchable graphs is co-NP-complete for any fixed $k \ge 2$. We provide a simple characterization for the class of strongly chordal graphs with equal $k$-packing and $k$-domination numbers. We also prove that for any fixed integer $\ell \ge 1$ the problem of finding a minimum weight maximal distance-$2\ell$ matching and the problem of finding a minimum weight $(2 \ell - 1)$-independent dominating set cannot be approximated in polynomial time in chordal graphs within a factor of $\delta \ln |V(G)|$ unless $\mathrm{P} = \mathrm{NP}$, where $\delta$ is a fixed constant (thereby improving the NP-hardness result of Chang for the independent domination case). Finally, we show the NP-hardness of the minimum maximal induced matching and independent dominating set problems in large-girth planar graphs.

---

Graphs of Edge-Intersecting Non-Splitting Paths in a Tree: Representations of Holes-Part II

Arman Boyacı ; Tınaz Ekim ; Mordechai Shalom ; Shmuel Zaks.

Given a tree and a set P of non-trivial simple paths on it, VPT(P) is the VPT graph (i.e. the vertex intersection graph) of the paths P, and EPT(P) is the EPT graph (i.e. the edge intersection graph) of P. These graphs have been extensively studied in the literature. Given two (edge) intersecting paths in a graph, their split vertices is the set of vertices having degree at least 3 in their union. A pair of (edge) intersecting paths is termed non-splitting if they do not have split vertices (namely if their union is a path). We define the graph ENPT(P) of edge intersecting non-splitting paths of a tree, termed the ENPT graph, as the graph having a vertex for each path in P, and an edge between every pair of vertices representing two paths that are both edge-intersecting and non-splitting. A graph G is an ENPT graph if there is a tree T and a set of paths P of T such that G=ENPT(P), and we say that is a representation of G. Our goal is to characterize the representation of chordless ENPT cycles (holes). To achieve this goal, we first assume that the EPT graph induced by the vertices of an ENPT hole is given. In [2] we introduce three assumptions (P1), (P2), (P3) defined on EPT, ENPT pairs of graphs. In the same study, we define two problems HamiltonianPairRec, P3-HamiltonianPairRec and characterize the representations of ENPT holes that satisfy (P1), (P2), (P3). In this work, we continue our work by relaxing these three assumptions one by one. We characterize the […]

---

Total Domination, Connected Vertex Cover and Steiner Tree with Conflicts

Alexis Cornet ; Christian Laforest.

Total dominating set, connected vertex cover and Steiner tree are well-known graph problems. Despite the fact that they are NP-complete to optimize, it is easy (even trivial) to find solutions, regardless of their size. In this paper, we study a variant of these problems by adding conflicts, that are pairs of vertices that cannot be both in a solution. This new constraint leads to situations where it is NP-complete to decide if there exists a solution avoiding conflicts. This paper proposes NP-completeness proofs of the existence of a solution for different restricted classes of graphs and conflicts, improving recent results. We also propose polynomial time constructions in several restricted cases and we introduce a new parameter, the stretch, to capture the locality of the conflicts.

---

A sufficient condition for a balanced bipartite digraph to be hamiltonian

Ruixia Wang.

We describe a new type of sufficient condition for a balanced bipartite digraph to be hamiltonian. Let $D$ be a balanced bipartite digraph and $x,y$ be distinct vertices in $D$. $\{x, y\}$ dominates a vertex $z$ if $x\rightarrow z$ and $y\rightarrow z$; in this case, we call the pair $\{x, y\}$ dominating. In this paper, we prove that a strong balanced bipartite digraph $D$ on $2a$ vertices contains a hamiltonian cycle if, for every dominating pair of vertices $\{x, y\}$, either $d(x)\ge 2a-1$ and $d(y)\ge a+1$ or $d(x)\ge a+1$ and $d(y)\ge 2a-1$. The lower bound in the result is sharp.

---

Circular Separation Dimension of a Subclass of Planar Graphs

Arpitha P. Bharathi ; Minati De ; Abhiruk Lahiri.

A pair of non-adjacent edges is said to be separated in a circular ordering of vertices, if the endpoints of the two edges do not alternate in the ordering. The circular separation dimension of a graph $G$, denoted by $\pi^\circ(G)$, is the minimum number of circular orderings of the vertices of $G$ such that every pair of non-adjacent edges is separated in at least one of the circular orderings. This notion is introduced by Loeb and West in their recent paper. In this article, we consider two subclasses of planar graphs, namely $2$-outerplanar graphs and series-parallel graphs. A $2$-outerplanar graph has a planar embedding such that the subgraph obtained by removal of the vertices of the exterior face is outerplanar. We prove that if $G$ is $2$-outerplanar then $\pi^\circ(G) = 2$. We also prove that if $G$ is a series-parallel graph then $\pi^\circ(G) \leq 2$.

---

On path-cycle decompositions of triangle-free graphs

Andrea Jiménez ; Yoshiko Wakabayashi.

In this work, we study conditions for the existence of length-constrained path-cycle decompositions, that is, partitions of the edge set of a graph into paths and cycles of a given minimum length. Our main contribution is the characterization of the class of all triangle-free graphs with odd distance at least $3$ that admit a path-cycle decomposition with elements of length at least $4$. As a consequence, it follows that Gallai's conjecture on path decomposition holds in a broad class of sparse graphs.

---

Tight upper bound on the maximum anti-forcing numbers of graphs

Lingjuan Shi ; Heping Zhang.

Let $G$ be a simple graph with a perfect matching. Deng and Zhang showed that the maximum anti-forcing number of $G$ is no more than the cyclomatic number. In this paper, we get a novel upper bound on the maximum anti-forcing number of $G$ and investigate the extremal graphs. If $G$ has a perfect matching $M$ whose anti-forcing number attains this upper bound, then we say $G$ is an extremal graph and $M$ is a nice perfect matching. We obtain an equivalent condition for the nice perfect matchings of $G$ and establish a one-to-one correspondence between the nice perfect matchings and the edge-involutions of $G$, which are the automorphisms $\alpha$ of order two such that $v$ and $\alpha(v)$ are adjacent for every vertex $v$. We demonstrate that all extremal graphs can be constructed from $K_2$ by implementing two expansion operations, and $G$ is extremal if and only if one factor in a Cartesian decomposition of $G$ is extremal. As examples, we have that all perfect matchings of the complete graph $K_{2n}$ and the complete bipartite graph $K_{n, n}$ are nice. Also we show that the hypercube $Q_n$, the folded hypercube $FQ_n$ ($n\geq4$) and the enhanced hypercube $Q_{n, k}$ ($0\leq k\leq n-4$) have exactly $n$, $n+1$ and $n+1$ nice perfect matchings respectively.

---

On rank-width of even-hole-free graphs

Isolde Adler ; Ngoc Khang Le ; Haiko Müller ; Marko Radovanović ; Nicolas Trotignon ; Kristina Vušković.

We present a class of (diamond, even hole)-free graphs with no clique cutset that has unbounded rank-width. In general, even-hole-free graphs have unbounded rank-width, because chordal graphs are even-hole-free. A.A. da Silva, A. Silva and C. Linhares-Sales (2010) showed that planar even-hole-free graphs have bounded rank-width, and N.K. Le (2016) showed that even-hole-free graphs with no star cutset have bounded rank-width. A natural question is to ask, whether even-hole-free graphs with no clique cutsets have bounded rank-width. Our result gives a negative answer. Hence we cannot apply Courcelle and Makowsky's meta-theorem which would provide efficient algorithms for a large number of problems, including the maximum independent set problem, whose complexity remains open for (diamond, even hole)-free graphs.

---

Irreversible 2-conversion set in graphs of bounded degree

Jan Kynčl ; Bernard Lidický ; Tomáš Vyskočil.

An irreversible $k$-threshold process (also a $k$-neighbor bootstrap percolation) is a dynamic process on a graph where vertices change color from white to black if they have at least $k$ black neighbors. An irreversible $k$-conversion set of a graph $G$ is a subset $S$ of vertices of $G$ such that the irreversible $k$-threshold process starting with $S$ black eventually changes all vertices of $G$ to black. We show that deciding the existence of an irreversible 2-conversion set of a given size is NP-complete, even for graphs of maximum degree 4, which answers a question of Dreyer and Roberts. Conversely, we show that for graphs of maximum degree 3, the minimum size of an irreversible 2-conversion set can be computed in polynomial time. Moreover, we find an optimal irreversible 3-conversion set for the toroidal grid, simplifying constructions of Pike and Zou.

---

Characterizations of minimal dominating sets and the well-dominated property in lexicographic product graphs

Didem Gözüpek ; Ademir Hujdurović ; Martin Milanič.

A graph is said to be well-dominated if all its minimal dominating sets are of the same size. The class of well-dominated graphs forms a subclass of the well studied class of well-covered graphs. While the recognition problem for the class of well-covered graphs is known to be co-NP-complete, the recognition complexity of well-dominated graphs is open. In this paper we introduce the notion of an irreducible dominating set, a variant of dominating set generalizing both minimal dominating sets and minimal total dominating sets. Based on this notion, we characterize the family of minimal dominating sets in a lexicographic product of two graphs and derive a characterization of the well-dominated lexicographic product graphs. As a side result motivated by this study, we give a polynomially testable characterization of well-dominated graphs with domination number two, and show, more generally, that well-dominated graphs can be recognized in polynomial time in any class of graphs with bounded domination number. Our results include a characterization of dominating sets in lexicographic product graphs, which generalizes the expression for the domination number of such graphs following from works of Zhang et al. (2011) and of \v{S}umenjak et al. (2012).

---

On a combination of the 1-2-3 Conjecture and the Antimagic Labelling Conjecture

Julien Bensmail ; Mohammed Senhaji ; Kasper Szabo Lyngsie.

This paper is dedicated to studying the following question: Is it always possible to injectively assign the weights 1, ..., |E(G)| to the edges of any given graph G (with no component isomorphic to K2) so that every two adjacent vertices of G get distinguished by their sums of incident weights? One may see this question as a combination of the well-known 1-2-3 Conjecture and the Antimagic Labelling Conjecture. Throughout this paper, we exhibit evidence that this question might be true. Benefiting from the investigations on the Antimagic Labelling Conjecture, we first point out that several classes of graphs, such as regular graphs, indeed admit such assignments. We then show that trees also do, answering a recent conjecture of Arumugam, Premalatha, Bača and Semaničová-Feňovčíková. Towards a general answer to the question above, we then prove that claimed assignments can be constructed for any graph, provided we are allowed to use some number of additional edge weights. For some classes of sparse graphs, namely 2-degenerate graphs and graphs with maximum average degree 3, we show that only a small (constant) number of such additional weights suffices.

---

Nonrepetitive edge-colorings of trees

A. Kündgen ; T. Talbot.

A repetition is a sequence of symbols in which the first half is the same as the second half. An edge-coloring of a graph is repetition-free or nonrepetitive if there is no path with a color pattern that is a repetition. The minimum number of colors so that a graph has a nonrepetitive edge-coloring is called its Thue edge-chromatic number. We improve on the best known general upper bound of $4\Delta-4$ for the Thue edge-chromatic number of trees of maximum degree $\Delta$ due to Alon, Grytczuk, Ha{\l}uszczak and Riordan (2002) by providing a simple nonrepetitive edge-coloring with $3\Delta-2$ colors.

---

Equivalence of the filament and overlap graphs of subtrees of limited trees

Jessica Enright ; Lorna Stewart.

The overlap graphs of subtrees of a tree are equivalent to subtree filament graphs, the overlap graphs of subtrees of a star are cocomparability graphs, and the overlap graphs of subtrees of a caterpillar are interval filament graphs. In this paper, we show the equivalence of many more classes of subtree overlap and subtree filament graphs, and equate them to classes of complements of cochordal-mixed graphs. Our results generalize the previously known results mentioned above.

---

Graphs of Edge-Intersecting and Non-Splitting One Bend Paths in a Grid

Arman Boyacı ; Tınaz Ekim ; Mordechai Shalom ; Shmuel Zaks.

The families EPT (resp. EPG) Edge Intersection Graphs of Paths in a tree (resp. in a grid) are well studied graph classes. Recently we introduced the graph classes Edge-Intersecting and Non-Splitting Paths in a Tree ENPT, and in a Grid (ENPG). It was shown that ENPG contains an infinite hierarchy of subclasses that are obtained by restricting the number of bends in the paths. Motivated by this result, in this work we focus on one bend {ENPG} graphs. We show that one bend ENPG graphs are properly included in two bend ENPG graphs. We also show that trees and cycles are one bend ENPG graphs, and characterize the split graphs and co-bipartite graphs that are one bend ENPG. We prove that the recognition problem of one bend ENPG split graphs is NP-complete even in a very restricted subfamily of split graphs. Last we provide a linear time recognition algorithm for one bend ENPG co-bipartite graphs.

---

The quotients between the (revised) Szeged index and Wiener index of graphs

Huihui Zhang ; Jing Chen ; Shuchao Li.

Let $Sz(G),Sz^*(G)$ and $W(G)$ be the Szeged index, revised Szeged index and Wiener index of a graph $G.$ In this paper, the graphs with the fourth, fifth, sixth and seventh largest Wiener indices among all unicyclic graphs of order $n\geqslant 10$ are characterized; as well the graphs with the first, second, third, and fourth largest Wiener indices among all bicyclic graphs are identified. Based on these results, further relation on the quotients between the (revised) Szeged index and the Wiener index are studied. Sharp lower bound on $Sz(G)/W(G)$ is determined for all connected graphs each of which contains at least one non-complete block. As well the connected graph with the second smallest value on $Sz^*(G)/W(G)$ is identified for $G$ containing at least one cycle.

---

The Existence of Planar Hypotraceable Oriented Graphs

Susan van Aardt ; Alewyn Petrus Burger ; Marietjie Frick.

A digraph is \emph{traceable} if it has a path that visits every vertex. A digraph $D$ is \emph{hypotraceable} if $D$ is not traceable but $D-v$ is traceable for every vertex $v\in V(D)$. It is known that there exists a planar hypotraceable digraph of order $n$ for every $n\geq 7$, but no examples of planar hypotraceable oriented graphs (digraphs without 2-cycles) have yet appeared in the literature. We show that there exists a planar hypotraceable oriented graph of order $n$ for every even $n \geq 10$, with the possible exception of $n = 14$.

---

A characterization of trees with equal 2-domination and 2-independence numbers

Christoph Brause ; Michael A. Henning ; Marcin Krzywkowski.

A set $S$ of vertices in a graph $G$ is a $2$-dominating set if every vertex of $G$ not in $S$ is adjacent to at least two vertices in $S$, and $S$ is a $2$-independent set if every vertex in $S$ is adjacent to at most one vertex of $S$. The $2$-domination number $\gamma_2(G)$ is the minimum cardinality of a $2$-dominating set in $G$, and the $2$-independence number $\alpha_2(G)$ is the maximum cardinality of a $2$-independent set in $G$. Chellali and Meddah [{\it Trees with equal $2$-domination and $2$-independence numbers,} Discussiones Mathematicae Graph Theory 32 (2012), 263--270] provided a constructive characterization of trees with equal $2$-domination and $2$-independence numbers. Their characterization is in terms of global properties of a tree, and involves properties of minimum $2$-dominating and maximum $2$-independent sets in the tree at each stage of the construction. We provide a constructive characterization that relies only on local properties of the tree at each stage of the construction.

---

A New Game Invariant of Graphs: the Game Distinguishing Number

Sylvain Gravier ; Kahina Meslem ; Simon Schmidt ; Souad Slimani.

The distinguishing number of a graph $G$ is a symmetry related graph invariant whose study started two decades ago. The distinguishing number $D(G)$ is the least integer $d$ such that $G$ has a $d$-distinguishing coloring. A distinguishing $d$-coloring is a coloring $c:V(G)\rightarrow\{1,...,d\}$ invariant only under the trivial automorphism. In this paper, we introduce a game variant of the distinguishing number. The distinguishing game is a game with two players, the Gentle and the Rascal, with antagonist goals. This game is played on a graph $G$ with a set of $d\in\mathbb N^*$ colors. Alternately, the two players choose a vertex of $G$ and color it with one of the $d$ colors. The game ends when all the vertices have been colored. Then the Gentle wins if the coloring is distinguishing and the Rascal wins otherwise. This game leads to define two new invariants for a graph $G$, which are the minimum numbers of colors needed to ensure that the Gentle has a winning strategy, depending on who starts. These invariants could be infinite, thus we start by giving sufficient conditions to have infinite game distinguishing numbers. We also show that for graphs with cyclic automorphisms group of prime odd order, both game invariants are finite. After that, we define a class of graphs, the involutive graphs, for which the game distinguishing number can be quadratically bounded above by the classical distinguishing number. The definition of this class is closely related to imprimitive […]

---

Mixing Times of Markov Chains on Degree Constrained Orientations of Planar Graphs

Stefan Felsner ; Daniel Heldt.

We study Markov chains for $\alpha$-orientations of plane graphs, these are orientations where the outdegree of each vertex is prescribed by the value of a given function $\alpha$. The set of $\alpha$-orientations of a plane graph has a natural distributive lattice structure. The moves of the up-down Markov chain on this distributive lattice corresponds to reversals of directed facial cycles in the $\alpha$-orientation. We have a positive and several negative results regarding the mixing time of such Markov chains. A 2-orientation of a plane quadrangulation is an orientation where every inner vertex has outdegree 2. We show that there is a class of plane quadrangulations such that the up-down Markov chain on the 2-orientations of these quadrangulations is slowly mixing. On the other hand the chain is rapidly mixing on 2-orientations of quadrangulations with maximum degree at most 4. Regarding examples for slow mixing we also revisit the case of 3-orientations of triangulations which has been studied before by Miracle et al.. Our examples for slow mixing are simpler and have a smaller maximum degree, Finally we present the first example of a function $\alpha$ and a class of plane triangulations of constant maximum degree such that the up-down Markov chain on the $\alpha$-orientations of these graphs is slowly mixing.

---

Linear recognition of generalized Fibonacci cubes $Q_h(111)$

Yoomi Rho ; Aleksander Vesel.

The generalized Fibonacci cube $Q_h(f)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. In particular, the vertex set of the 3rd order generalized Fibonacci cube $Q_h(111)$ is the set of all binary strings $b_1b_2 \ldots b_h$ containing no three consecutive 1's. We present a new characterization of the 3rd order generalized Fibonacci cubes based on their recursive structure. The characterization is the basis for an algorithm which recognizes these graphs in linear time.

---

Matchings of quadratic size extend to long cycles in hypercubes

Tomáš Dvořák.

Ruskey and Savage in 1993 asked whether every matching in a hypercube can be extended to a Hamiltonian cycle. A positive answer is known for perfect matchings, but the general case has been resolved only for matchings of linear size. In this paper we show that there is a quadratic function $q(n)$ such that every matching in the $n$-dimensional hypercube of size at most $q(n)$ may be extended to a cycle which covers at least $\frac34$ of the vertices.

---

Connected Tropical Subgraphs in Vertex-Colored Graphs

Jean-Alexandre Anglès d'Auriac ; Nathann Cohen ; Hakim El Mafthoui ; Ararat Harutyunyan ; Sylvain Legay ; Yannis Manoussakis.

A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the graph. In this work we study the problem of finding a minimal connected tropical subgraph. We first show that this problem is NP-Hard for trees, interval graphs and split graphs, but polynomial when the number of colors is logarithmic in terms of the order of the graph (i.e. FPT). We then provide upper bounds for the order of the minimal connected tropical subgraph under various conditions. We finally study the problem of finding a connected tropical subgraph in a randomly vertex-colored random graph.

---

An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed size

De-Yan Zeng ; Jian-Hua Yin.

A graph $G$ is a $2$-tree if $G=K_3$, or $G$ has a vertex $v$ of degree 2, whose neighbors are adjacent, and $G-v$ is a 2-tree. Clearly, if $G$ is a 2-tree on $n$ vertices, then $|E(G)|=2n-3$. A non-increasing sequence $\pi =(d_1, \ldots ,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. Yin and Li (Acta Mathematica Sinica, English Series, 25(2009)795–802) proved that if $k \geq 2$, $n \geq \frac{9}{2}k^2 + \frac{19}{2}k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > (k-2)n$, then $\pi$ has a realization containing every tree on $k$ vertices as a subgraph. Moreover, the lower bound $(k-2)n$ is the best possible. This is a variation of a conjecture due to Erdős and Sós. In this paper, we investigate an analogue extremal problem for 2-trees and prove that if $k \geq 3$, $n \geq 2k^2-k$ and $\pi =(d_1, \ldots ,d_n)$ is a graphic sequence with $\sum \limits_{i=1}^n d_i > \frac{4kn}{3} - \frac{5n}{3}$ then $\pi$ has a realization containing every 2-tree on $k$ vertices as a subgraph. We also show that the lower bound $\frac{4kn}{3} - \frac{5n}{3}$ is almost the best possible.

---

On degree-sequence characterization and the extremal number of edges for various Hamiltonian properties under fault tolerance

Shih-Yan Chen ; Shin-Shin Kao ; Hsun Su.

Assume that $n, \delta ,k$ are integers with $0 \leq k < \delta < n$. Given a graph $G=(V,E)$ with $|V|=n$. The symbol $G-F, F \subseteq V$, denotes the graph with $V(G-F)=V-F$, and $E(G-F)$ obtained by $E$ after deleting the edges with at least one endvertex in $F$. $G$ is called $k$-vertex fault traceable, $k$-vertex fault Hamiltonian, or $k$-vertex fault Hamiltonian-connected if $G-F$ remains traceable, Hamiltonian, and Hamiltonian-connected for all $F$ with $0 \leq |F| \leq k$, respectively. The notations $h_1(n, \delta ,k)$, $h_2(n, \delta ,k)$, and $h_3(n, \delta ,k)$ denote the minimum number of edges required to guarantee an $n$-vertex graph with minimum degree $\delta (G) \geq \delta$ to be $k$-vertex fault traceable, $k$-vertex fault Hamiltonian, and $k$-vertex fault Hamiltonian-connected, respectively. In this paper, we establish a theorem which uses the degree sequence of a given graph to characterize the $k$-vertex fault traceability/hamiltonicity/Hamiltonian-connectivity, respectively. Then we use this theorem to obtain the formulas for $h_i(n, \delta ,k)$ for $1 \leq i \leq 3$, which improves and extends the known results for $k=0$.

---

Edge Disjoint Hamilton Cycles in Knödel Graphs

Palanivel Subramania Nadar Paulraja ; S Sampath Kumar.

The vertices of the Knödel graph $W_{\Delta, n}$ on $n \geq 2$ vertices, $n$ even, and of maximum degree $\Delta, 1 \leq \Delta \leq \lfloor log_2(n) \rfloor$, are the pairs $(i,j)$ with $i=1,2$ and $0 \leq j \leq \frac{n}{2} -1$. For $0 \leq j \leq \frac{n}{2} -1$, there is an edge between vertex $(1,j)$ and every vertex $(2,j + 2^k - 1 (mod \frac{n}{2}))$, for $k=0,1,2, \ldots , \Delta -1$. Existence of a Hamilton cycle decomposition of $W_{k, 2k}, k \geq 6$ is not yet known, see Discrete Appl. Math. 137 (2004) 173-195. In this paper, it is shown that the $k$-regular Knödel graph $W_{k,2k}, k \geq 6$ has $ \lfloor \frac{k}{2} \rfloor - 1$ edge disjoint Hamilton cycles.

---

Traceability of locally hamiltonian and locally traceable graphs

Johan De Wet ; Susan Van Aardt.

If $\mathcal{P}$ is a given graph property, we say that a graph $G$ is locally $\mathcal{P}$ if $\langle N(v) \rangle$ has property $\mathcal{P}$ for every $v \in V(G)$ where $\langle N(v) \rangle$ is the induced graph on the open neighbourhood of the vertex $v$. Pareek and Skupien (C. M. Pareek and Z. Skupien , On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983) posed the following two questions. Question 1 Is 9 the smallest order of a connected nontraceable locally traceable graph? Question 2 Is 14 the smallest order of a connected nontraceable locally hamiltonian graph? We answer the second question in the affirmative, but show that the correct number for the first question is 10. We develop a technique to construct connected locally hamiltonian and locally traceable graphs that are not traceable. We use this technique to construct such graphs with various prescribed properties.

---

The inapproximability for the $(0,1)$-additive number

Arash Ahadi ; Ali Dehghan.

An additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$ ($x \sim y$ means that $x$ is joined to $y$). The additive number of $G$, denoted by $\eta (G)$, is the minimum number $k$ such that $G$ has a additive labeling $\ell : V(G) \rightarrow \mathbb{N}_k$. The additive choosability of a graph $G$, denoted by $\eta_\ell (G)$, is the smallest number $k$ such that $G$ has an additive labeling for any assignment of lists of size $k$ to the vertices of $G$, such that the label of each vertex belongs to its own list. Seamone in his PhD thesis conjectured that for every graph $G$, $\eta(G)= \eta_\ell (G)$. We give a negative answer to this conjecture and we show that for every $k$ there is a graph $G$ such that $\eta_\ell (G) - \eta(G) \geq k$. A $(0,1)$-additive labeling of a graph $G$ is a function $\ell :V(G) \rightarrow \{0,1 \}$, such that for every two adjacent vertices $v$ and $u$ of $G$, $\Sigma_{w \sim v} \ell (w) \neq \Sigma_{w \sim u} \ell (w)$. A graph may lack any $(0,1)$-additive labeling. We show that it is NP-complete to decide whether a $(0,1)$-additive labeling exists for some families of graphs such as perfect graphs and planar triangle-free graphs. For a graph $G$ with some $(0,1)$-additive labelings, the $(0,1)$-additive number of $G$ is defined as $\sigma_1 (G) = \mathrm{min}_{\ell \in \Gamma} […]

---

The irregularity of two types of trees

Li Jianxi ; Yang Liu ; Wai Shiu.

The irregularity of a graph $G$ is defined as the sum of weights $|d(u)-d(v)|$ of all edges $uv$ of $G$, where $d(u)$ and $d(v)$ are the degrees of the vertices $u$ and $v$ in $G$, respectively. In this paper, some structural properties on trees with maximum (or minimum) irregularity among trees with given degree sequence and trees with given branching number are explored, respectively. Moreover, the corresponding trees with maximum (or minimum) irregularity are also found, respectively.

---

Partitioning the vertex set of $G$ to make $G\,\Box\, H$ an efficient open domination graph

Tadeja Kraner Šumenjak ; Iztok Peterin ; Douglas F. Rall ; Aleksandra Tepeh.

A graph is an efficient open domination graph if there exists a subset of vertices whose open neighborhoods partition its vertex set. We characterize those graphs $G$ for which the Cartesian product $G \Box H$ is an efficient open domination graph when $H$ is a complete graph of order at least 3 or a complete bipartite graph. The characterization is based on the existence of a certain type of weak partition of $V(G)$. For the class of trees when $H$ is complete of order at least 3, the characterization is constructive. In addition, a special type of efficient open domination graph is characterized among Cartesian products $G \Box H$ when $H$ is a 5-cycle or a 4-cycle.

---

Planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable

Marthe Bonamy ; Benjamin Lévêque ; Alexandre Pinlou.

For planar graphs, we consider the problems of list edge coloring and list total coloring. Edge coloring is the problem of coloring the edges while ensuring that two edges that are adjacent receive different colors. Total coloring is the problem of coloring the edges and the vertices while ensuring that two edges that are adjacent, two vertices that are adjacent, or a vertex and an edge that are incident receive different colors. In their list extensions, instead of having the same set of colors for the whole graph, every vertex or edge is assigned some set of colors and has to be colored from it. A graph is minimally edge or total choosable if it is list $\Delta$-edge-colorable or list $(\Delta +1)$-total-colorable, respectively, where $\Delta$ is the maximum degree in the graph. It is already known that planar graphs with $\Delta \geq 8$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable (Li Xu 2011), and that planar graphs with $\Delta \geq 7$ and no triangle sharing a vertex with a $C_4$ or no triangle adjacent to a $C_k (\forall 3 \leq k \leq 6)$ are minimally total colorable (Wang Wu 2011). We strengthen here these results and prove that planar graphs with $\Delta \geq 7$ and no triangle adjacent to a $C_4$ are minimally edge and total choosable.

---

Rainbow eulerian multidigraphs and the product of cycles

Susana López ; Francesc-Antoni Muntaner-Batle.

An arc colored eulerian multidigraph with $l$ colors is rainbow eulerian if there is an eulerian circuit in which a sequence of $l$ colors repeats. The digraph product that refers the title was introduced by Figueroa-Centeno et al. as follows: let $D$ be a digraph and let $\Gamma$ be a family of digraphs such that $V(F)=V$ for every $F\in \Gamma$. Consider any function $h:E(D) \longrightarrow \Gamma$. Then the product $D \otimes_h \Gamma$ is the digraph with vertex set $V(D) \times V$ and $((a,x),(b,y)) \in E(D \otimes_h \Gamma)$ if and only if $(a,b) \in E(D)$ and $(x,y) \in E(h (a,b))$. In this paper we use rainbow eulerian multidigraphs and permutations as a way to characterize the $\otimes_h$-product of oriented cycles. We study the behavior of the $\otimes_h$-product when applied to digraphs with unicyclic components. The results obtained allow us to get edge-magic labelings of graphs formed by the union of unicyclic components and with different magic sums.

---

Heredity for generalized power domination

Paul Dorbec ; Seethu Varghese ; Ambat Vijayakumar.

In this paper, we study the behaviour of the generalized power domination number of a graph by small changes on the graph, namely edge and vertex deletion and edge contraction. We prove optimal bounds for $\gamma_{p,k}(G-e)$, $\gamma_{p,k}(G/e)$ and for $\gamma_{p,k}(G-v)$ in terms of $\gamma_{p,k}(G)$, and give examples for which these bounds are tight. We characterize all graphs for which $\gamma_{p,k}(G-e) = \gamma_{p,k}(G)+1$ for any edge $e$. We also consider the behaviour of the propagation radius of graphs by similar modifications.

---

Open k-monopolies in graphs: complexity and related concepts

Dorota Kuziak ; Iztok Peterin ; Ismael G. Yero.

Closed monopolies in graphs have a quite long range of applications in several problems related to overcoming failures, since they frequently have some common approaches around the notion of majorities, for instance to consensus problems, diagnosis problems or voting systems. We introduce here open $k$-monopolies in graphs which are closely related to different parameters in graphs. Given a graph $G=(V,E)$ and $X\subseteq V$, if $\delta_X(v)$ is the number of neighbors $v$ has in $X$, $k$ is an integer and $t$ is a positive integer, then we establish in this article a connection between the following three concepts: - Given a nonempty set $M\subseteq V$ a vertex $v$ of $G$ is said to be $k$-controlled by $M$ if $\delta_M(v)\ge \frac{\delta_V(v)}{2}+k$. The set $M$ is called an open $k$-monopoly for $G$ if it $k$-controls every vertex $v$ of $G$. - A function $f: V\rightarrow \{-1,1\}$ is called a signed total $t$-dominating function for $G$ if $f(N(v))=\sum_{v\in N(v)}f(v)\geq t$ for all $v\in V$. - A nonempty set $S\subseteq V$ is a global (defensive and offensive) $k$-alliance in $G$ if $\delta_S(v)\ge \delta_{V-S}(v)+k$ holds for every $v\in V$. In this article we prove that the problem of computing the minimum cardinality of an open $0$-monopoly in a graph is NP-complete even restricted to bipartite or chordal graphs. In addition we present some general bounds for the minimum cardinality of open $k$-monopolies and we derive some exact values.

---

Edge-partitioning graphs into regular and locally irregular components

Julien Bensmail ; Brett Stevens.

A graph is locally irregular if every two adjacent vertices have distinct degrees. Recently, Baudon et al. introduced the notion of decomposition into locally irregular subgraphs. They conjectured that for almost every graph $G$, there exists a minimum integer $\chi^{\prime}_{\mathrm{irr}}(G)$ such that $G$ admits an edge-partition into $\chi^{\prime}_{\mathrm{irr}}(G)$ classes, each of which induces a locally irregular graph. In particular, they conjectured that $\chi^{\prime}_{\mathrm{irr}}(G) \leq 3$ for every $G$, unless $G$ belongs to a well-characterized family of non-decomposable graphs. This conjecture is far from being settled, as notably (1) no constant upper bound on$\chi^{\prime}_{\mathrm{irr}}(G)$ is known for $G$ bipartite, and (2) no satisfactory general upper bound on $\chi^{\prime}_{\mathrm{irr}}(G)$ is known. We herein investigate the consequences on this question of allowing a decomposition to include regular components as well. As a main result, we prove that every bipartite graph admits such a decomposition into at most $6$ subgraphs. This result implies that every graph $G$ admits a decomposition into at most $6(\lfloor \mathrm{log} \chi (G) \rfloor +1)$ subgraphs whose components are regular or locally irregular.

---

The complexity of deciding whether a graph admits an orientation with fixed weak diameter

Julien Bensmail ; Romaric Duvignau ; Sergey Kirgizov.

An oriented graph $\overrightarrow{G}$ is said weak (resp. strong) if, for every pair $\{ u,v \}$ of vertices of $\overrightarrow{G}$, there are directed paths joining $u$ and $v$ in either direction (resp. both directions). In case, for every pair of vertices, some of these directed paths have length at most $k$, we call $\overrightarrow{G}$ $k$-weak (resp. $k$-strong). We consider several problems asking whether an undirected graph $G$ admits orientations satisfying some connectivity and distance properties. As a main result, we show that deciding whether $G$ admits a $k$-weak orientation is NP-complete for every $k \geq 2$. This notably implies the NP-completeness of several problems asking whether $G$ is an extremal graph (in terms of needed colours) for some vertex-colouring problems.

---

Vertex-Coloring Edge-Weighting of Bipartite Graphs with Two Edge Weights

Hongliang Lu.

Let $G$ be a graph and $\mathcal{S}$ be a subset of $Z$. A vertex-coloring $\mathcal{S}$-edge-weighting of $G$ is an assignment of weights by the elements of $\mathcal{S}$ to each edge of $G$ so that adjacent vertices have different sums of incident edges weights. It was proved that every 3-connected bipartite graph admits a vertex-coloring $\mathcal{S}$-edge-weighting for $\mathcal{S} = \{1,2 \}$ (H. Lu, Q. Yu and C. Zhang, Vertex-coloring 2-edge-weighting of graphs, European J. Combin., 32 (2011), 22-27). In this paper, we show that every 2-connected and 3-edge-connected bipartite graph admits a vertex-coloring $\mathcal{S}$-edge-weighting for $\mathcal{S} \in \{ \{ 0,1 \} , \{1,2 \} \}$. These bounds we obtain are tight, since there exists a family of infinite bipartite graphs which are 2-connected and do not admit vertex-coloring $\mathcal{S}$-edge-weightings for $\mathcal{S} \in \{ \{ 0,1 \} , \{1,2 \} \}$.

---

The double competition multigraph of a digraph

Yoshio Sano ; Jeongmi Park.

In this article, we introduce the notion of the double competition multigraph of a digraph. We give characterizations of the double competition multigraphs of arbitrary digraphs, loopless digraphs, reflexive digraphs, and acyclic digraphs in terms of edge clique partitions of the multigraphs.

---

The game colouring number of powers of forests

Stephan Dominique Andres ; Winfried Hochstättler.

We prove that the game colouring number of the $m$-th power of a forest of maximum degree $\Delta\ge3$ is bounded from above by \[\frac{(\Delta-1)^m-1}{\Delta-2}+2^m+1,\] which improves the best known bound by an asymptotic factor of 2.

---

Cubical coloring — fractional covering by cuts and semidefinite programming

Robert Šámal.

We introduce a new graph parameter that measures fractional covering of a graph by cuts. Besides being interesting in its own right, it is useful for study of homomorphisms and tension-continuous mappings. We study the relations with chromatic number, bipartite density, and other graph parameters. We find the value of our parameter for a family of graphs based on hypercubes. These graphs play for our parameter the role that cliques play for the chromatic number and Kneser graphs for the fractional chromatic number. The fact that the defined parameter attains on these graphs the correct value suggests that our definition is a natural one. In the proof we use the eigenvalue bound for maximum cut and a recent result of Engström, Färnqvist, Jonsson, and Thapper [An approximability-related parameter on graphs – properties and applications, DMTCS vol. 17:1, 2015, 33–66]. We also provide a polynomial time approximation algorithm based on semidefinite programming and in particular on vector chromatic number (defined by Karger, Motwani and Sudan [Approximate graph coloring by semidefinite programming, J. ACM 45 (1998), no. 2, 246–265]).

---

Disimplicial arcs, transitive vertices, and disimplicial eliminations

Martiniano Eguia ; Francisco Soulignac.

In this article we deal with the problems of finding the disimplicial arcs of a digraph and recognizing some interesting graph classes defined by their existence. A diclique of a digraph is a pair $V$ → $W$ of sets of vertices such that $v$ → $w$ is an arc for every $v$ ∈ $V$ and $w$ ∈ $W$. An arc $v$ → $w$ is disimplicial when it belongs to a unique maximal diclique. We show that the problem of finding the disimplicial arcs is equivalent, in terms of time and space complexity, to that of locating the transitive vertices. As a result, an efficient algorithm to find the bisimplicial edges of bipartite graphs is obtained. Then, we develop simple algorithms to build disimplicial elimination schemes, which can be used to generate bisimplicial elimination schemes for bipartite graphs. Finally, we study two classes related to perfect disimplicial elimination digraphs, namely weakly diclique irreducible digraphs and diclique irreducible digraphs. The former class is associated to finite posets, while the latter corresponds to dedekind complete finite posets.

---

Packing Plane Perfect Matchings into a Point Set

Ahmad Biniaz ; Prosenjit Bose ; Anil Maheshwari ; Michiel Smid.

Given a set $P$ of $n$ points in the plane, where $n$ is even, we consider the following question: How many plane perfect matchings can be packed into $P$? For points in general position we prove the lower bound of ⌊log₂$n$⌋$-1$. For some special configurations of point sets, we give the exact answer. We also consider some restricted variants of this problem.

---

The complexity of $P$₄-decomposition of regular graphs and multigraphs

Ajit Diwan ; Justine Dion ; David Mendell ; Michael Plantholt ; Shailesh Tipnis.

Let G denote a multigraph with edge set E(G), let µ(G) denote the maximum edge multiplicity in G, and let Pk denote the path on k vertices. Heinrich et al.(1999) showed that P4 decomposes a connected 4-regular graph G if and only if |E(G)| is divisible by 3. We show that P4 decomposes a connected 4-regular multigraph G with µ(G) ≤2 if and only if no 3 vertices of G induce more than 4 edges and |E(G)| is divisible by 3. Oksimets (2003) proved that for all integers k ≥3, P4 decomposes a connected 2k-regular graph G if and only if |E(G)| is divisible by 3. We prove that for all integers k ≥2, the problem of determining if P4 decomposes a (2k + 1)-regular graph is NP-Complete. El-Zanati et al.(2014) showed that for all integers k ≥1, every 6k-regular multigraph with µ(G) ≤2k has a P4-decomposition. We show that unless P = NP, this result is best possible with respect to µ(G) by proving that for all integers k ≥3 the problem of determining if P4 decomposes a 2k-regular multigraph with µ(G) ≤⌊2k / 3 ⌋+ 1 is NP-Complete.

---

On graphs double-critical with respect to the colouring number

Matthias Kriesell ; Anders Pedersen.

The colouring number col($G$) of a graph $G$ is the smallest integer $k$ for which there is an ordering of the vertices of $G$ such that when removing the vertices of $G$ in the specified order no vertex of degree more than $k-1$ in the remaining graph is removed at any step. An edge $e$ of a graph $G$ is said to be double-col-critical if the colouring number of $G-V(e)$ is at most the colouring number of $G$ minus 2. A connected graph G is said to be double-col-critical if each edge of $G$ is double-col-critical. We characterise the double-col-critical graphs with colouring number at most 5. In addition, we prove that every 4-col-critical non-complete graph has at most half of its edges being double-col-critical, and that the extremal graphs are precisely the odd wheels on at least six vertices. We observe that for any integer $k$ greater than 4 and any positive number $ε$, there is a $k$-col-critical graph with the ratio of double-col-critical edges between $1- ε$ and 1.

---

The game chromatic number of trees and forests

Charles Dunn ; Victor Larsen ; Kira Lindke ; Troy Retter ; Dustin Toci.

While the game chromatic number of a forest is known to be at most 4, no simple criteria are known for determining the game chromatic number of a forest. We first state necessary and sufficient conditions for forests with game chromatic number 2 and then investigate the differences between forests with game chromatic number 3 and 4. In doing so, we present a minimal example of a forest with game chromatic number 4, criteria for determining in polynomial time the game chromatic number of a forest without vertices of degree 3, and an example of a forest with maximum degree 3 and game chromatic number 4. This gives partial progress on the open question of the computational complexity of the game chromatic number of a forest.

---

Snarks with total chromatic number 5

Gunnar Brinkmann ; Myriam Preissmann ; Diana Sasaki.

A k-total-coloring of G is an assignment of k colors to the edges and vertices of G, so that adjacent and incident elements have different colors. The total chromatic number of G, denoted by χT(G), is the least k for which G has a k-total-coloring. It was proved by Rosenfeld that the total chromatic number of a cubic graph is either 4 or 5. Cubic graphs with χT = 4 are said to be Type 1, and cubic graphs with χT = 5 are said to be Type 2. Snarks are cyclically 4-edge-connected cubic graphs that do not allow a 3-edge-coloring. In 2003, Cavicchioli et al. asked for a Type 2 snark with girth at least 5. As neither Type 2 cubic graphs with girth at least 5 nor Type 2 snarks are known, this is taking two steps at once, and the two requirements of being a snark and having girth at least 5 should better be treated independently. In this paper we will show that the property of being a snark can be combined with being Type 2. We will give a construction that gives Type 2 snarks for each even vertex number n≥40. We will also give the result of a computer search showing that among all Type 2 cubic graphs on up to 32 vertices, all but three contain an induced chordless cycle of length 4. These three exceptions contain triangles. The question of the existence of a Type 2 cubic graph with girth at least 5 remains open.

---

Maximum difference about the size of optimal identifying codes in graphs differing by one vertex

Mikko Pelto.

Let G=(V,E) be a simple undirected graph. We call any subset C⊆V an identifying code if the sets I(v)={c∈C | {v,c}∈E or v=c } are distinct and non-empty for all vertices v∈V. A graph is called twin-free if there is an identifying code in the graph. The identifying code with minimum size in a twin-free graph G is called the optimal identifying code and the size of such a code is denoted by γ(G). Let GS denote the induced subgraph of G where the vertex set S⊂V is deleted. We provide a tight upper bound for γ(GS)-γ(G) when both graphs are twin-free and |V| is large enough with respect to |S|. Moreover, we prove tight upper bound when G is a bipartite graph and |S|=1.

---

Graphs with large disjunctive total domination number

Michael A. Henning ; Viroshan Naicker.

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, γdt(G), is the minimum cardinality of such a set. We observe that γdt(G) ≤γt(G). Let G be a connected graph on n vertices with minimum degree δ. It is known [J. Graph Theory 35 (2000), 21 13;45] that if δ≥2 and n ≥11, then γt(G) ≤4n/7. Further [J. Graph Theory 46 (2004), 207 13;210] if δ≥3, then γt(G) ≤n/2. We prove that if δ≥2 and n ≥8, then γdt(G) ≤n/2 and we characterize the extremal graphs.

---

Extending a perfect matching to a Hamiltonian cycle

Adel Alahmadi ; Robert E. L. Aldred ; Ahmad Alkenani ; Rola Hijazi ; P. Solé ; Carsten Thomassen.

Ruskey and Savage conjectured that in the d-dimensional hypercube, every matching M can be extended to a Hamiltonian cycle. Fink verified this for every perfect matching M, remarkably even if M contains external edges. We prove that this property also holds for sparse spanning regular subgraphs of the cubes: for every d ≥7 and every k, where 7 ≤k ≤d, the d-dimensional hypercube contains a k-regular spanning subgraph such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle. We do not know if this result can be extended to k=4,5,6. It cannot be extended to k=3. Indeed, there are only three 3-regular graphs such that every perfect matching (possibly with external edges) can be extended to a Hamiltonian cycle, namely the complete graph on 4 vertices, the complete bipartite 3-regular graph on 6 vertices and the 3-cube on 8 vertices. Also, we do not know if there are graphs of girth at least 5 with this matching-extendability property.

---

A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs

Olga Bodroža-Pantić ; Harris Kwong ; Milan Pantić.

We study the enumeration of Hamiltonian cycles on the thin grid cylinder graph $C_m \times P_{n+1}$. We distinguish two types of Hamiltonian cycles, and denote their numbers $h_m^A(n)$ and $h_m^B(n)$. For fixed $m$, both of them satisfy linear homogeneous recurrence relations with constant coefficients, and we derive their generating functions and other related results for $m\leq10$. The computational data we gathered suggests that $h^A_m(n)\sim h^B_m(n)$ when $m$ is even.

---

On probe 2-clique graphs and probe diamond-free graphs

Flavia Bonomo ; Celina M. H. Figueiredo ; Guillermo Duran ; Luciano N. Grippo ; Martín D. Safe ; Jayme L. Szwarcfiter.

Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the resulting graph belongs to G. We investigate probe 2-clique graphs and probe diamond-free graphs. For probe 2-clique graphs, we present a polynomial-time recognition algorithm. Probe diamond-free graphs are characterized by minimal forbidden induced subgraphs. As a by-product, it is proved that the class of probe block graphs is the intersection between the classes of chordal graphs and probe diamond-free graphs.

---

p-box: a new graph model

Mauricio Soto ; Christopher Thraves-Caro.

In this document, we study the scope of the following graph model: each vertex is assigned to a box in ℝd and to a representative element that belongs to that box. Two vertices are connected by an edge if and only if its respective boxes contain the opposite representative element. We focus our study on the case where boxes (and therefore representative elements) associated to vertices are spread in ℝ. We give both, a combinatorial and an intersection characterization of the model. Based on these characterizations, we determine graph families that contain the model (e. g., boxicity 2 graphs) and others that the new model contains (e. g., rooted directed path). We also study the particular case where each representative element is the center of its respective box. In this particular case, we provide constructive representations for interval, block and outerplanar graphs. Finally, we show that the general and the particular model are not equivalent by constructing a graph family that separates the two cases.

---

Guarded subgraphs and the domination game

Boštjan Brešar ; Sandi Klavžar ; Gasper Košmrlj ; Doug F. Rall.

We introduce the concept of guarded subgraph of a graph, which as a condition lies between convex and 2-isometric subgraphs and is not comparable to isometric subgraphs. Some basic metric properties of guarded subgraphs are obtained, and then this concept is applied to the domination game. In this game two players, Dominator and Staller, alternate choosing vertices of a graph, one at a time, such that each chosen vertex enlarges the set of vertices dominated so far. The aim of Dominator is that the graph is dominated in as few steps as possible, while the aim of Staller is just the opposite. The game domination number is the number of vertices chosen when Dominator starts the game and both players play optimally. The main result of this paper is that the game domination number of a graph is not smaller than the game domination number of any guarded subgraph. Several applications of this result are presented.

---

Edge stability in secure graph domination

Anton Pierre Burger ; Alewyn Petrus Villiers ; Jan Harm Vuuren.

A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X-v)∪u is again a dominating set of G. The secure domination number of G is the cardinality of a smallest secure dominating set of G. A graph G is p-stable if the largest arbitrary subset of edges whose removal from G does not increase the secure domination number of the resulting graph, has cardinality p. In this paper we study the problem of computing p-stable graphs for all admissible values of p and determine the exact values of p for which members of various infinite classes of graphs are p-stable. We also consider the problem of determining analytically the largest value ωn of p for which a graph of order n can be p-stable. We conjecture that ωn=n-2 and motivate this conjecture.

---

Connectivity of Fibonacci cubes, Lucas cubes and generalized cubes

Jernej Azarija ; Sandi Klavžar ; Jaehun Lee ; Yoomi Rho.

If f is a binary word and d a positive integer, then the generalized Fibonacci cube Qd(f) is the graph obtained from the d-cube Qd by removing all the vertices that contain f as a factor, while the generalized Lucas cube Qd(lucas(f)) is the graph obtained from Qd by removing all the vertices that have a circulation containing f as a factor. The Fibonacci cube Γd and the Lucas cube Λd are the graphs Qd(11) and Qd(lucas(11)), respectively. It is proved that the connectivity and the edge-connectivity of Γd as well as of Λd are equal to ⌊ d+2 / 3⌋. Connected generalized Lucas cubes are characterized and generalized Fibonacci cubes are proved to be 2-connected. It is asked whether the connectivity equals minimum degree also for all generalized Fibonacci/Lucas cubes. It was checked by computer that the answer is positive for all f and all d≤9.

---

Symmetric bipartite graphs and graphs with loops

Grant Cairns ; Stacey Mendan.

We show that if the two parts of a finite bipartite graph have the same degree sequence, then there is a bipartite graph, with the same degree sequences, which is symmetric, in that it has an involutive graph automorphism that interchanges its two parts. To prove this, we study the relationship between symmetric bipartite graphs and graphs with loops.

---

On the 1-2-3-conjecture

Akbar Davoodi ; Behnaz Omoomi.

A k-edge-weighting of a graph G is a function w:E(G)→{1,…,k}. An edge-weighting naturally induces a vertex coloring c, where for every vertex v∈V(G), c(v)=∑e∼vw(e). If the induced coloring c is a proper vertex coloring, then w is called a vertex-coloring k-edge-weighting (VC k-EW). Karoński et al. (J. Combin. Theory Ser. B, 91 (2004) 151 13;157) conjectured that every graph admits a VC 3-EW. This conjecture is known as the 1-2-3-conjecture. In this paper, first, we study the vertex-coloring edge-weighting of the Cartesian product of graphs. We prove that if the 1-2-3-conjecture holds for two graphs G and H, then it also holds for G□H. Also we prove that the Cartesian product of connected bipartite graphs admits a VC 2-EW. Moreover, we present several sufficient conditions for a graph to admit a VC 2-EW. Finally, we explore some bipartite graphs which do not admit a VC 2-EW.

---

An approximability-related parameter on graphs―-properties and applications

Robert Engström ; Tommy Färnqvist ; Peter Jonsson ; Johan Thapper.

We introduce a binary parameter on optimisation problems called separation. The parameter is used to relate the approximation ratios of different optimisation problems; in other words, we can convert approximability (and non-approximability) result for one problem into (non)-approximability results for other problems. Our main application is the problem (weighted) maximum H-colourable subgraph (Max H-Col), which is a restriction of the general maximum constraint satisfaction problem (Max CSP) to a single, binary, and symmetric relation. Using known approximation ratios for Max k-cut, we obtain general asymptotic approximability results for Max H-Col for an arbitrary graph H. For several classes of graphs, we provide near-optimal results under the unique games conjecture. We also investigate separation as a graph parameter. In this vein, we study its properties on circular complete graphs. Furthermore, we establish a close connection to work by Šámal on cubical colourings of graphs. This connection shows that our parameter is closely related to a special type of chromatic number. We believe that this insight may turn out to be crucial for understanding the behaviour of the parameter, and in the longer term, for understanding the approximability of optimisation problems such as Max H-Col.

---

Ore-degree threshold for the square of a Hamiltonian cycle

Louis DeBiasio ; Safi Faizullah ; Imdadullah Khan.

A classic theorem of Dirac from 1952 states that every graph with minimum degree at least n=2 contains a Hamiltonian cycle. In 1963, P´osa conjectured that every graph with minimum degree at least 2n=3 contains the square of a Hamiltonian cycle. In 1960, Ore relaxed the degree condition in the Dirac’s theorem by proving that every graph with deg(u) + deg(v) ≥ n for every uv =2 E(G) contains a Hamiltonian cycle. Recently, Chˆau proved an Ore-type version of P´osa’s conjecture for graphs on n ≥ n0 vertices using the regularity–blow-up method; consequently the n0 is very large (involving a tower function). Here we present another proof that avoids the use of the regularity lemma. Aside from the fact that our proof holds for much smaller n0, we believe that our method of proof will be of independent interest.

---

Generalized dynamic storage allocation

H. A. Kierstead ; Karin R. Saoub.

Dynamic Storage Allocation is a problem concerned with storing items that each have weight and time restrictions. Approximate algorithms have been constructed through online coloring of interval graphs. We present a generalization that uses online coloring of tolerance graphs. We utilize online-with-representation algorithms on tolerance graphs, which are online algorithms in which the corresponding tolerance representation of a vertex is also presented. We find linear bounds for the online-with-representation chromatic number of various classes of tolerance graphs and apply these results to a generalization of Dynamic Storage Allocation, giving us a polynomial time approximation algorithm with linear performance ratio.

---

Toppling numbers of complete and random graphs

Anthony Bonato ; William B. Kinnersley ; Pawel Pralat.

We study a two-person game played on graphs based on the widely studied chip-firing game. Players Max and Min alternately place chips on the vertices of a graph. When a vertex accumulates as many chips as its degree, it fires, sending one chip to each neighbour; this may in turn cause other vertices to fire. The game ends when vertices continue firing forever. Min seeks to minimize the number of chips played during the game, while Max seeks to maximize it. When both players play optimally, the length of the game is the toppling number of a graph G, and is denoted by t(G). By considering strategies for both players and investigating the evolution of the game with differential equations, we provide asymptotic bounds on the toppling number of the complete graph. In particular, we prove that for sufficiently large n 0.596400 n2 < t(Kn) < 0.637152 n2. Using a fractional version of the game, we couple the toppling numbers of complete graphs and the binomial random graph G(n,p). It is shown that for pn ≥n² / √ log(n) asymptotically almost surely t(G(n,p))=(1+o(1)) p t(Kn).

---

Partitioning the vertex set of a bipartite graph into complete bipartite subgraphs

Oleg Duginov.

Given a graph and a positive integer k, the biclique vertex-partition problem asks whether the vertex set of the graph can be partitioned into at most k bicliques (connected complete bipartite subgraphs). It is known that this problem is NP-complete for bipartite graphs. In this paper we investigate the computational complexity of this problem in special subclasses of bipartite graphs. We prove that the biclique vertex-partition problem is polynomially solvable for bipartite permutation graphs, bipartite distance-hereditary graphs and remains NP-complete for perfect elimination bipartite graphs and bipartite graphs containing no 4-cycles as induced subgraphs.

---

Packing and covering the balanced complete bipartite multigraph with cycles and stars

Hung-Chih Lee.

Let Ck denote a cycle of length k and let Sk denote a star with k edges. For multigraphs F, G and H, an (F,G)-decomposition of H is an edge decomposition of H into copies of F and G using at least one of each. For L⊆H and R⊆rH, an (F,G)-packing (resp. (F,G)-covering) of H with leave L (resp. padding R) is an (F,G)-decomposition of H-E(L) (resp. H+E(R)). An (F,G)-packing (resp. (F,G)-covering) of H with the largest (resp. smallest) cardinality is a maximum (F,G)-packing (resp. minimum (F,G)-covering), and its cardinality is referred to as the (F,G)-packing number (resp. (F,G)-covering number) of H. In this paper, we determine the packing number and the covering number of λKn,n with Ck's and Sk's for any λ, n and k, and give the complete solution of the maximum packing and the minimum covering of λKn,n with 4-cycles and 4-stars for any λ and n with all possible leaves and paddings.

---

Bounding the monomial index and (1,l)-weight choosability of a graph

Ben Seamone.

Let G = (V,E) be a graph. For each e ∈E(G) and v ∈V(G), let Le and Lv, respectively, be a list of real numbers. Let w be a function on V(G) ∪E(G) such that w(e) ∈Le for each e ∈E(G) and w(v) ∈Lv for each v ∈V(G), and let cw be the vertex colouring obtained by cw(v) = w(v) + ∑ₑ ∋vw(e). A graph is (k,l)-weight choosable if there exists a weighting function w for which cw is proper whenever |Lv| ≥k and |Le| ≥l for every v ∈V(G) and e ∈E(G). A sufficient condition for a graph to be (1,l)-weight choosable was developed by Bartnicki, Grytczuk and Niwczyk (2009), based on the Combinatorial Nullstellensatz, a parameter which they call the monomial index of a graph, and matrix permanents. This paper extends their method to establish the first general upper bound on the monomial index of a graph, and thus to obtain an upper bound on l for which every admissible graph is (1,l)-weight choosable. Let ∂2(G) denote the smallest value s such that every induced subgraph of G has vertices at distance 2 whose degrees sum to at most s. We show that every admissible graph has monomial index at most ∂2(G) and hence that such graphs are (1, ∂2(G)+1)-weight choosable. While this does not improve the best known result on (1,l)-weight choosability, we show that the results can be extended to obtain improved bounds for some graph products; for instance, it is shown that G □ Kn is (1, nd+3)-weight choosable if G is d-degenerate.

---

Genus distributions of cubic series-parallel graphs

Jonathan L. Gross ; Michal Kotrbčík ; Timothy Sun.

We derive a quadratic-time algorithm for the genus distribution of any 3-regular, biconnected series-parallel graph, which we extend to any biconnected series-parallel graph of maximum degree at most 3. Since the biconnected components of every graph of treewidth 2 are series-parallel graphs, this yields, by use of bar-amalgamation, a quadratic-time algorithm for every graph of treewidth at most 2 and maximum degree at most 3.

---

Complexity of conditional colouring with given template

Peter J. Dukes ; Steve Lowdon ; Gary Macgillivray.

We study partitions of the vertex set of a given graph into cells that each induce a subgraph in a given family, and for which edges can have ends in different cells only when those cells correspond to adjacent vertices of a fixed template graph H. For triangle-free templates, a general collection of graph families for which the partitioning problem can be solved in polynomial time is described. For templates with a triangle, the problem is in some cases shown to be NP-complete.

---

Oriented diameter and rainbow connection number of a graph

Xiaolong Huang ; Hengzhe Li ; Xueliang Li ; Yuefang Sun.

The oriented diameter of a bridgeless graph G is min diam(H) | H is a strang orientation of G. A path in an edge-colored graph G, where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. The rainbow connection number rc(G) of G is the smallest integer number k for which there exists a k-edge-coloring of G such that every two distinct vertices of G are connected by a rainbow path. In this paper, we obtain upper bounds for the oriented diameter and the rainbow connection number of a graph in terms of rad(G) and η(G), where rad(G) is the radius of G and η(G) is the smallest integer number such that every edge of G is contained in a cycle of length at most η(G). We also obtain constant bounds of the oriented diameter and the rainbow connection number for a (bipartite) graph G in terms of the minimum degree of G.

---

Balancedness of subclasses of circular-arc graphs

Flavia Bonomo ; Guillermo Duran ; Martın D. Safe ; Annegret K. Wagler.

A graph is balanced if its clique-vertex incidence matrix contains no square submatrix of odd order with exactly two ones per row and per column. There is a characterization of balanced graphs by forbidden induced subgraphs, but no characterization by mininal forbidden induced subgraphs is known, not even for the case of circular-arc graphs. A circular-arc graph is the intersection graph of a family of arcs on a circle. In this work, we characterize when a given graph G is balanced in terms of minimal forbidden induced subgraphs, by restricting the analysis to the case where G belongs to certain classes of circular-arc graphs, including Helly circular-arc graphs, claw-free circular-arc graphs, and gem-free circular-arc graphs. In the case of gem-free circular-arc graphs, analogous characterizations are derived for two superclasses of balanced graphs: clique-perfect graphs and coordinated graphs.

---

A four-sweep LBFS recognition algorithm for interval graphs

Peng Li ; Yaokun Wu.

In their 2009 paper, Corneil et al. design a linear time interval graph recognition algorithm based on six sweeps of Lexicographic Breadth-First Search (LBFS) and prove its correctness. They believe that their corresponding 5-sweep LBFS interval graph recognition algorithm is also correct. Thanks to the LBFS structure theory established mainly by Corneil et al., we are able to present a 4-sweep LBFS algorithm which determines whether or not the input graph is a unit interval graph or an interval graph. Like the algorithm of Corneil et al., our algorithm does not involve any complicated data structure and can be executed in linear time.

---

The generalized 3-connectivity of Lexicographic product graphs

Xueliang Li ; Yaping Mao.

The generalized k-connectivity κk(G) of a graph G, first introduced by Hager, is a natural generalization of the concept of (vertex-)connectivity. Denote by G^H and G&Box;H the lexicographic product and Cartesian product of two graphs G and H, respectively. In this paper, we prove that for any two connected graphs G and H, κ3(G^H)≥ κ3(G)|V(H)|. We also give upper bounds for κ3(G&Box; H) and κ3(G^H). Moreover, all the bounds are sharp.

---

On the Meyniel condition for hamiltonicity in bipartite digraphs

Janusz Adamus ; Lech Adamus ; Anders Yeo.

We prove a sharp Meyniel-type criterion for hamiltonicity of a balanced bipartite digraph: For a≥2, a strongly connected balanced bipartite digraph D on 2a vertices is hamiltonian if d(u)+d(v)≥3a whenever uv∉A(D) and vu∉A(D). As a consequence, we obtain a sharp sufficient condition for hamiltonicity in terms of the minimal degree: a strongly connected balanced bipartite digraph D on 2a vertices is hamiltonian if δ(D)≥3a/2.

---

A variant of Niessen’s problem on degreesequences of graphs

Jiyun Guo ; Jianhua Yin.

Let (a1,a2,\textellipsis,an) and (b1,b2,\textellipsis,bn) be two sequences of nonnegative integers satisfying the condition that b1>=b2>=...>=bn, ai<= bi for i=1,2,\textellipsis,n and ai+bi>=ai+1+bi+1 for i=1,2,\textellipsis, n-1. In this paper, we give two different conditions, one of which is sufficient and the other one necessary, for the sequences (a1,a2,\textellipsis,an) and (b1,b2,\textellipsis,bn) such that for every (c1,c2,\textellipsis,cn) with ai<=ci<=bi for i=1,2,\textellipsis,n and ∑&limits;i=1n ci=0 (mod 2), there exists a simple graph G with vertices v1,v2,\textellipsis,vn such that dG(vi)=ci for i=1,2,\textellipsis,n. This is a variant of Niessen\textquoterights problem on degree sequences of graphs (Discrete Math., 191 (1998), 247–253).

---

The Price of Connectivity for Vertex Cover

Eglantine Camby ; Jean Cardinal ; Samuel Fiorini ; Oliver Schaudt.

The vertex cover number of a graph is the minimum number of vertices that are needed to cover all edges. When those vertices are further required to induce a connected subgraph, the corresponding number is called the connected vertex cover number, and is always greater or equal to the vertex cover number. Connected vertex covers are found in many applications, and the relationship between those two graph invariants is therefore a natural question to investigate. For that purpose, we introduce the \em Price of Connectivity, defined as the ratio between the two vertex cover numbers. We prove that the price of connectivity is at most 2 for arbitrary graphs. We further consider graph classes in which the price of connectivity of every induced subgraph is bounded by some real number t. We obtain forbidden induced subgraph characterizations for every real value t ≤q 3/2. We also investigate critical graphs for this property, namely, graphs whose price of connectivity is strictly greater than that of any proper induced subgraph. Those are the only graphs that can appear in a forbidden subgraph characterization for the hereditary property of having a price of connectivity at most t. In particular, we completely characterize the critical graphs that are also chordal. Finally, we also consider the question of computing the price of connectivity of a given graph. Unsurprisingly, the decision version of this question is NP-hard. In fact, we show that it is even complete for the class […]

---

On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph

Olivier Baudon ; Julien Bensmail ; Rafał Kalinowski ; Antoni Marczyk ; Jakub Przybyło ; Mariusz Wozniak.

A graph G of order n is called arbitrarily partitionable (AP, for short) if, for every sequence τ=(n1,\textellipsis,nk) of positive integers that sum up to n, there exists a partition (V1,\textellipsis,Vk) of the vertex set V(G) such that each set Vi induces a connected subgraph of order ni. A graph G is called AP+1 if, given a vertex u∈V(G) and an index q∈ {1,\textellipsis,k}, such a partition exists with u∈Vq. We consider the Cartesian product of AP graphs. We prove that if G is AP+1 and H is traceable, then the Cartesian product G□ H is AP+1. We also prove that G□H is AP, whenever G and H are AP and the order of one of them is not greater than four.

---

The total irregularity of a graph

Hosam Abdo ; Stephan Brandt ; D. Dimitrov.

In this note a new measure of irregularity of a graph G is introduced. It is named the total irregularity of a graph and is defined as irr(t)(G) - 1/2 Sigma(u, v is an element of V(G)) vertical bar d(G)(u) - d(G)(v)vertical bar, where d(G)(u) denotes the degree of a vertex u is an element of V(G). All graphs with maximal total irregularity are determined. It is also shown that among all trees of the same order the star has the maximal total irregularity.

---

Strong parity vertex coloring of plane graphs

Tomas Kaiser ; Ondrej Rucky ; Matej Stehlik ; Riste Škrekovski.

A strong parity vertex coloring of a 2-connected plane graph is a coloring of the vertices such that every face is incident with zero or an odd number of vertices of each color. We prove that every 2-connected loopless plane graph has a strong parity vertex coloring with 97 colors. Moreover the coloring we construct is proper. This proves a conjecture of Czap and Jendrol' [Discuss. Math. Graph Theory 29 (2009), pp. 521-543.]. We also provide examples showing that eight colors may be necessary (ten when restricted to proper colorings).

---

Efficient open domination in graph products

Dorota Kuziak ; Iztok Peterin ; Ismael Gonzalez Yero.

A graph G is an efficient open domination graph if there exists a subset D of V(G) for which the open neighborhoods centered in vertices of D form a partition of V(G). We completely describe efficient open domination graphs among lexicographic, strong, and disjunctive products of graphs. For the Cartesian product we give a characterization when one factor is K2.

---

List circular backbone colouring

Frédéric Havet ; Andrew King.

A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, depending on whether or not the edge is in the backbone. In this paper we consider the list version of this problem, with particular focus on colours in ℤp - this problem is closely related to the problem of circular choosability. We first prove that the list circular q-backbone chromatic number of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs.

---

On Hamiltonian Paths and Cycles in Sufficiently Large Distance Graphs

Christian Löwenstein ; Dieter Rautenbach ; Roman Soták.

For a positive integer n∈ℕ and a set D⊆ ℕ, the distance graph GnD has vertex set { 0,1,\textellipsis,n-1} and two vertices i and j of GnD are adjacent exactly if |j-i|∈D. The condition gcd(D)=1 is necessary for a distance graph GnD being connected. Let D={d1,d2}⊆ℕ be such that d1>d2 and gcd(d1,d2)=1. We prove the following results. If n is sufficiently large in terms of D, then GnD has a Hamiltonian path with endvertices 0 and n-1. If d1d2 is odd, n is even and sufficiently large in terms of D, then GnD has a Hamiltonian cycle. If d1d2 is even and n is sufficiently large in terms of D, then GnD has a Hamiltonian cycle.

---

On size, radius and minimum degree

Simon Mukwembi.

Let G be a finite connected graph. We give an asymptotically tight upper bound on the size of G in terms of order, radius and minimum degree. Our result is a strengthening of an old classical theorem of Vizing (1967) if minimum degree is prescribed.

---

The resolving number of a graph Delia

Delia Garijo ; Antonio González ; Alberto Márquez.

We study a graph parameter related to resolving sets and metric dimension, namely the resolving number, introduced by Chartrand, Poisson and Zhang. First, we establish an important difference between the two parameters: while computing the metric dimension of an arbitrary graph is known to be NP-hard, we show that the resolving number can be computed in polynomial time. We then relate the resolving number to classical graph parameters: diameter, girth, clique number, order and maximum degree. With these relations in hand, we characterize the graphs with resolving number 3 extending other studies that provide characterizations for smaller resolving number.

---

1-local 33/24-competitive Algorithm for Multicoloring Hexagonal Graphs

Rafal Witkowski ; Janez Žerovnik.

In the frequency allocation problem, we are given a cellular telephone network whose geographical coverage area is divided into cells, where phone calls are serviced by assigned frequencies, so that none of the pairs of calls emanating from the same or neighboring cells is assigned the same frequency. The problem is to use the frequencies efficiently, i.e. minimize the span of frequencies used. The frequency allocation problem can be regarded as a multicoloring problem on a weighted hexagonal graph, where each vertex knows its position in the graph. We present a 1-local 33/24-competitive distributed algorithm for multicoloring a hexagonal graph, thereby improving the previous 1-local 7/5-competitive algorithm.

---

A new characterization and a recognition algorithm of Lucas cubes

Andrej Taranenko.

Fibonacci and Lucas cubes are induced subgraphs of hypercubes obtained by excluding certain binary strings from the vertex set. They appear as models for interconnection networks, as well as in chemistry. We derive a characterization of Lucas cubes that is based on a peripheral expansion of a unique convex subgraph of an appropriate Fibonacci cube. This serves as the foundation for a recognition algorithm of Lucas cubes that runs in linear time.

---

Clique cycle transversals in graphs with few P₄'s

Raquel Bravo ; Sulamita Klein ; Loana Tito Nogueira ; Fábio Protti.

A graph is extended P4-laden if each of its induced subgraphs with at most six vertices that contains more than two induced P4's is 2K2,C4-free. A cycle transversal (or feedback vertex set) of a graph G is a subset T ⊆ V (G) such that T ∩ V (C) 6= ∅ for every cycle C of G; if, in addition, T is a clique, then T is a clique cycle transversal (cct). Finding a cct in a graph G is equivalent to partitioning V (G) into subsets C and F such that C induces a complete subgraph and F an acyclic subgraph. This work considers the problem of characterizing extended P4-laden graphs admitting a cct. We characterize such graphs by means of a finite family of forbidden induced subgraphs, and present a linear-time algorithm to recognize them.

---

Maximal independent sets in bipartite graphs with at least one cycle

Shuchao Li ; Huihui Zhang ; Xiaoyan Zhang.

A maximal independent set is an independent set that is not a proper subset of any other independent set. Liu [J.Q. Liu, Maximal independent sets of bipartite graphs, J. Graph Theory, 17 (4) (1993) 495-507] determined the largest number of maximal independent sets among all n-vertex bipartite graphs. The corresponding extremal graphs are forests. It is natural and interesting for us to consider this problem on bipartite graphs with cycles. Let \mathscrBₙ (resp. \mathscrBₙ') be the set of all n-vertex bipartite graphs with at least one cycle for even (resp. odd) n. In this paper, the largest number of maximal independent sets of graphs in \mathscrBₙ (resp. \mathscrBₙ') is considered. Among \mathscrBₙ the disconnected graphs with the first-, second-, \ldots, \fracn-22-th largest number of maximal independent sets are characterized, while the connected graphs in \mathscrBₙ having the largest, the second largest number of maximal independent sets are determined. Among \mathscrBₙ' graphs have the largest number of maximal independent sets are identified.

---

A note on the NP-hardness of two matching problems in induced subgrids

Marc Demange ; Tınaz Ekim.

Given a graph, finding the maximal matching of minimum size (MMM) and the induced matching of maximum size (MIM) have been very popular research topics during the last decades. In this paper, we give new complexity results, namely the NP-hardness of MMM and MIM in induced subgrids and we point out some promising research directions. We also sketch the general framework of a unified approach to show the NP-hardness of some problems in subgrids.

---

Probe interval graphs and probe unit interval graphs on superclasses of cographs

Flavia Bonomo ; Guillermo Durán ; Luciano N. Grippo ; Martın D. Safe.

A graph is probe (unit) interval if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a (unit) interval graph by adding edges with both endpoints in the set of nonprobe vertices. Probe (unit) interval graphs form a superclass of (unit) interval graphs. Probe interval graphs were introduced by Zhang for an application concerning the physical mapping of DNA in the human genome project. The main results of this article are minimal forbidden induced subgraphs characterizations of probe interval and probe unit interval graphs within two superclasses of cographs: P4-tidy graphs and tree-cographs. Furthermore, we introduce the concept of graphs class with a companion which allows to describe all the minimally non-(probe G) graphs with disconnected complement for every graph class G with a companion.

---

Removable edges in near-bricks

Xiumei Wang ; Cheng He ; Yixun Lin.

For a brick apart from a few small graphs, Lovász (1987) proposed a conjecture on the existence of an edge whose deletion results in a graph with only one brick in its tight cut decomposition. Carvalho, Lucchesi, and Murty (2002) confirmed this conjecture by showing the existence of such two edges. This paper generalizes the result obtained by Carvalho et al. to the case of irreducible near-brick, where a graph is irreducible if it contains no induced odd path of length 3 or more. Meanwhile, a lower bound on the number of removable edges of matching-covered bipartite graphs is presented.

---

Improved bounds on the crossing number of butterfly network

Paul D. Manuel ; Bharati Rajan ; Indra Rajasingh ; P. Vasanthi Beulah.

We draw the r-dimensional butterfly network with 1 / 44r+O(r2r) crossings which improves the previous estimate given by Cimikowski (1996). We also give a lower bound which matches the upper bound obtained in this paper.

---

Bipartite powers of k-chordal graphs

Sunil Chandran ; Rogers Mathew.

Let k be an integer and k ≥3. A graph G is k-chordal if G does not have an induced cycle of length greater than k. From the definition it is clear that 3-chordal graphs are precisely the class of chordal graphs. Duchet proved that, for every positive integer m, if Gm is chordal then so is Gm+2. Brandstädt et al. in [Andreas Brandstädt, Van Bang Le, and Thomas Szymczak. Duchet-type theorems for powers of HHD-free graphs. Discrete Mathematics, 177(1-3):9-16, 1997.] showed that if Gm is k-chordal, then so is Gm+2. Powering a bipartite graph does not preserve its bipartitedness. In order to preserve the bipartitedness of a bipartite graph while powering Chandran et al. introduced the notion of bipartite powering. This notion was introduced to aid their study of boxicity of chordal bipartite graphs. The m-th bipartite power G[m] of a bipartite graph G is the bipartite graph obtained from G by adding edges (u,v) where dG(u,v) is odd and less than or equal to m. Note that G[m] = G[m+1] for each odd m. In this paper we show that, given a bipartite graph G, if G is k-chordal then so is G[m], where k, m are positive integers with k≥4.

---

The b-chromatic number of powers of cycles

Anja Kohl.

A b-coloring of a graph G by k colors is a proper vertex coloring such that each color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k-1 color classes. The b-chromatic number χb(G) is the maximum integer k for which G has a b-coloring by k colors. Let Cnr be the rth power of a cycle of order n. In 2003, Effantin and Kheddouci established the b-chromatic number χb(Cnr) for all values of n and r, except for 2r+3≤n≤3r. For the missing cases they presented the lower bound L:= min n-r-1,r+1+⌊ n-r-1 / 3⌋ and conjectured that χb(Cnr)=L. In this paper, we determine the exact value on χb(Cnr) for the missing cases. It turns out that χb(Cnr)>L for 2r+3≤n≤2r+3+r-6 / 4.

---

All totally symmetric colored graphs

Mariusz Grech ; Andrzej Kisielewicz.

In this paper we describe all edge-colored graphs that are fully symmetric with respect to colors and transitive on every set of edges of the same color. They correspond to fully symmetric homogeneous factorizations of complete graphs. Our description completes the work done in our previous paper, where we have shown, in particular, that there are no such graphs with more than 5 colors. Using some recent results, with a help of computer, we settle all the cases that was left open in the previous paper.

---

A chip-firing variation and a new proof of Cayley's formula

Peter Mark Kayll ; Dave Perkins.

We introduce a variation of chip-firing games on connected graphs. These 'burn-off' games incorporate the loss of energy that may occur in the physical processes that classical chip-firing games have been used to model. For a graph G=(V,E), a configuration of 'chips' on its nodes is a mapping C:V→ℕ. We study the configurations that can arise in the course of iterating a burn-off game. After characterizing the 'relaxed legal' configurations for general graphs, we enumerate the 'legal' ones for complete graphs Kn. The number of relaxed legal configurations on Kn coincides with the number tn+1 of spanning trees of Kn+1. Since our algorithmic, bijective proof of this fact does not invoke Cayley's Formula for tn, our main results yield secondarily a new proof of this formula.

---

Krausz dimension and its generalizations in special graph classes

Olga Glebova ; Yury Metelsky ; Pavel Skums.

A Krausz (k,m)-partition of a graph G is a decomposition of G into cliques, such that any vertex belongs to at most k cliques and any two cliques have at most m vertices in common. The m-Krausz dimension kdimm(G) of the graph G is the minimum number k such that G has a Krausz (k,m)-partition. In particular, 1-Krausz dimension or simply Krausz dimension kdim(G) is a well-known graph-theoretical parameter. In this paper we prove that the problem "kdim(G)≤3" is polynomially solvable for chordal graphs, thus partially solving the open problem of P. Hlineny and J. Kratochvil. We solve another open problem of P. Hlineny and J. Kratochvil by proving that the problem of finding Krausz dimension is NP-hard for split graphs and complements of bipartite graphs. We show that the problem of finding m-Krausz dimension is NP-hard for every m≥1, but the problem "kdimm(G)≤k" is is fixed-parameter tractable when parameterized by k and m for (∞,1)-polar graphs. Moreover, the class of (∞,1)-polar graphs with kdimm(G)≤k is characterized by a finite list of forbidden induced subgraphs for every k,m≥1.

---

Further results on maximal nontraceable graphs of smallest size

Alewyn Petrus Burger ; Joy Elizabeth Singleton.

Let g(n) denote the minimum number of edges of a maximal nontraceable (MNT) graph of order n. In 2005 Frick and Singleton (Lower bound for the size of maximal nontraceable graphs, Electronic Journal of Combinatorics, 12(1) R32, 2005) proved that g(n) = ⌈3n-22 ⌉ for n ≥54 as well as for n ∈I, where I= 12,13,22,23,30,31,38,39, 40,41,42,43,46,47,48,49,50,51 and they determined g(n) for n ≤9. We determine g(n) for 18 of the remaining 26 values of n, showing that g(n) = ⌈ 3n-22 ⌉ for n ≥54 as well as for n ∈I ∪18,19,20,21,24,25,26,27,28, 29,32,33 and g(n) = ⌈ 3n2 ⌉ for n ∈ 10, 11, 14, 15, 16, 17. We give results based on ''analytic'' proofs as well as computer searches.

---

The determining number of Kneser graphs

José Cáceres ; Delia Garijo ; Antonio González ; Alberto Márquez ; Marıa Luz Puertas.

A set of vertices S is a determining set of a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G is the minimum cardinality of a determining set of G. This paper studies the determining number of Kneser graphs. First, we compute the determining number of a wide range of Kneser graphs, concretely Kn:k with n≥k(k+1) / 2+1. In the language of group theory, these computations provide exact values for the base size of the symmetric group Sn acting on the k-subsets of 1,..., n. Then, we establish for which Kneser graphs Kn:k the determining number is equal to n-k, answering a question posed by Boutin. Finally, we find all Kneser graphs with fixed determining number 5, extending the study developed by Boutin for determining number 2, 3 or 4.

---

Sequence variations of the 1-2-3 conjecture and irregularity strength

Ben Seamone ; Brett Stevens.

Karonski, Luczak, and Thomason (2004) conjecture that, for any connected graph G on at least three vertices, there exists an edge weighting from 1, 2, 3 such that adjacent vertices receive different sums of incident edge weights. Bartnicki, Grytczuk, and Niwcyk (2009) make a stronger conjecture, that each edge's weight may be chosen from an arbitrary list of size 3 rather than 1, 2, 3. We examine a variation of these conjectures, where each vertex is coloured with a sequence of edge weights. Such a colouring relies on an ordering of E(G), and so two variations arise - one where we may choose any ordering of E(G) and one where the ordering is fixed. In the former case, we bound the list size required for any graph. In the latter, we obtain a bound on list sizes for graphs with sufficiently large minimum degree. We also extend our methods to a list variation of irregularity strength, where each vertex receives a distinct sequence of edge weights.

---

Upper k-tuple domination in graphs

Gerard Jennhwa Chang ; Paul Dorbec ; Hye Kyung Kim ; André Raspaud ; Haichao Wang ; Weiliang Zhao.

For a positive integer k, a k-tuple dominating set of a graph G is a subset S of V (G) such that |N [v] ∩ S| ≥ k for every vertex v, where N [v] = {v} ∪ {u ∈ V (G) : uv ∈ E(G)}. The upper k-tuple domination number of G, denoted by Γ×k (G), is the maximum cardinality of a minimal k-tuple dominating set of G. In this paper we present an upper bound on Γ×k (G) for r-regular graphs G with r ≥ k, and characterize extremal graphs achieving the upper bound. We also establish an upper bound on Γ×2 (G) for claw-free r-regular graphs. For the algorithmic aspect, we show that the upper k-tuple domination problem is NP-complete for bipartite graphs and for chordal graphs.

---

Secure frameproof codes through biclique covers

Hossein Hajiabolhassan ; Farokhlagha Moazami.

For a binary code Γ of length v, a v-word w produces by a set of codewords {w1,...,wr}⊆Γ if for all i=1,...,v, we have wi∈{w1i,...,wri} . We call a code r-secure frameproof of size t if |Γ|=t and for any v-word that is produced by two sets C1 and C2 of size at most r then the intersection of these sets is nonempty. A d-biclique cover of size v of a graph G is a collection of v-complete bipartite subgraphs of G such that each edge of G belongs to at least d of these complete bipartite subgraphs. In this paper, we show that for t≥2r, an r-secure frameproof code of size t and length v exists if and only if there exists a 1-biclique cover of size v for the Kneser graph KG(t,r) whose vertices are all r-subsets of a t-element set and two r-subsets are adjacent if their intersection is empty. Then we investigate some connection between the minimum size of d-biclique covers of Kneser graphs and cover-free families, where an (r,w;d) cover-free family is a family of subsets of a finite set such that the intersection of any r members of the family contains at least d elements that are not in the union of any other w members. Also, we present an upper bound for 1-biclique covering number of Kneser graphs.

---

A note on planar Ramsey numbers for a triangle versus wheels

Guofei Zhou ; Yaojun Chen ; Zhengke Miao ; Shariefuddin Pirzada.

For two given graphs G and H , the planar Ramsey number P R ( G; H ) is the smallest integer n such that every planar graph F on n vertices either contains a copy of G , or its complement contains a copy of H . In this paper, we determine all planar Ramsey numbers for a triangle versus wheels.

---

On 4-valent Frobenius circulant graphs

Sanming Zhou.

A 4-valent first-kind Frobenius circulant graph is a connected Cayley graph DLn(1, h) = Cay(Zn, H) on the additive group of integers modulo n, where each prime factor of n is congruent to 1 modulo 4 and H = {[1], [h], −[1], −[h]} with h a solution to the congruence equation x 2 + 1 ≡ 0 (mod n). In [A. Thomson and S. Zhou, Frobenius circulant graphs of valency four, J. Austral. Math. Soc. 85 (2008), 269-282] it was proved that such graphs admit 'perfect ' routing and gossiping schemes in some sense, making them attractive candidates for modelling interconnection networks. In the present paper we prove that DLn(1, h) has the smallest possible broadcasting time, namely its diameter plus two, and we explicitly give an optimal broadcasting in DLn(1, h). Using number theory we prove that it is possible to recursively construct larger 4-valent first-kind Frobenius circulants from smaller ones, and we give a methodology for such a construction. These and existing results suggest that, among all 4-valent circulant graphs, 4-valent first-kind Frobenius circulants are extremely efficient in terms of routing, gossiping, broadcasting and recursive construction.

---

Immersion containment and connectivity in color-critical graphs

Faisal N. Abu-Khzam ; Michael A. Langston.

The relationship between graph coloring and the immersion order is considered. Vertex connectivity, edge connectivity and related issues are explored. It is shown that a t-chromatic graph G contains either an immersed Kt or an immersed t-chromatic subgraph that is both 4-vertex-connected and t-edge-connected. This gives supporting evidence of our conjecture that if G requires at least t colors, then Kt is immersed in G.

---

Acyclic chromatic index of fully subdivided graphs and Halin graphs

Manu Basavaraju.

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a'(G). A graph G is called fully subdivided if it is obtained from another graph H by replacing every edge by a path of length at least two. Fully subdivided graphs are known to be acyclically edge colorable using Δ+1 colors since they are properly contained in 2-degenerate graphs which are acyclically edge colorable using Δ+1 colors. Muthu, Narayanan and Subramanian gave a simple direct proof of this fact for the fully subdivided graphs. Fiamcik has shown that if we subdivide every edge in a cubic graph with at most two exceptions to get a graph G, then a'(G)=3. In this paper we generalise the bound to Δ for all fully subdivided graphs improving the result of Muthu et al. In particular, we prove that if G is a fully subdivided graph and Δ(G) ≥3, then a'(G)=Δ(G). Consider a graph G=(V,E), with E=E(T) ∪E(C) where T is a rooted tree on the vertex set V and C is a simple cycle on the leaves of T. Such a graph G is called a Halin graph if G has a planar embedding and T has no vertices of degree 2. Let Kn denote a complete graph on n vertices. Let G be a Halin graph with maximum degree Δ. We prove that, a'(G) = 5 if G is K4, 4 if Δ = 3 and G is not K4, and Δ otherwise.

---

Random Cayley digraphs of diameter 2 and given degree

Manuel E. Lladser ; Primož Potočnik ; Jozef Širáň ; Mark C. Wilson.

We consider random Cayley digraphs of order n with uniformly distributed generating sets of size k. Specifically, we are interested in the asymptotics of the probability that such a Cayley digraph has diameter two as n -> infinity and k = f(n), focusing on the functions f(n) = left perpendicularn(delta)right perpendicular and f(n) = left perpendicularcnright perpendicular. In both instances we show that this probability converges to 1 as n -> infinity for arbitrary fixed delta is an element of (1/2, 1) and c is an element of (0, 1/2), respectively, with a much larger convergence rate in the second case and with sharper results for Abelian groups.

---

Graphs with many vertex-disjoint cycles

Dieter Rautenbach ; Friedrich Regen.

We study graphs G in which the maximum number of vertex-disjoint cycles nu(G) is close to the cyclomatic number mu(G), which is a natural upper bound for nu(G). Our main result is the existence of a finite set P(k) of graphs for all k is an element of N-0 such that every 2-connected graph G with mu(G)-nu(G) = k arises by applying a simple extension rule to a graph in P(k). As an algorithmic consequence we describe algorithms calculating minmu(G)-nu(G), k + 1 in linear time for fixed k.

---

On paths, trails and closed trails in edge-colored graphs

Laurent Gourvès ; Adria Lyra ; Carlos A. Martinhon ; Jérôme Monnot.

In this paper we deal from an algorithmic perspective with different questions regarding properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph G(c), we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex is specified before hand. As a consequence, we solve a number of interesting related problems. For instance, given subset S of vertices in G(c), we show how to maximize in polynomial time the number of S-restricted vertex (resp., edge) disjoint PEC paths (resp., trails) in G(c) with endpoints in S. Further, if G(c) contains no PEC closed trails, we show that the problem of finding a PEC s-t trail visiting a given subset of vertices can be solved in polynomial time and prove that it becomes NP-complete if we are restricted to graphs with no PEC cycles. We also deal with graphs G(c) containing no (almost) PEC cycles or closed trails through s or t. We prove that finding 2 PEC s-t paths (resp., trails) with length at most L > 0 is NP-complete in the strong sense even for graphs with maximum degree equal to 3 and present an approximation algorithm for computing k vertex (resp., edge) disjoint PEC s-t paths (resp., trails) so that the maximum path (resp., trail) length is no more than k times the PEC path (resp., trail) length in an optimal solution. Further, we prove that finding 2 vertex disjoint s-t paths with exactly one PEC s-t path is NP-complete. This result is interesting since […]

---

The competition number of a generalized line graph is at most two

Boram Park ; Yoshio Sano.

In 1982, Opsut showed that the competition number of a line graph is at most two and gave a necessary and sufficient condition for the competition number of a line graph being one. In this paper, we generalize this result to the competition numbers of generalized line graphs, that is, we show that the competition number of a generalized line graph is at most two, and give necessary conditions and sufficient conditions for the competition number of a generalized line graph being one.

---

On bipartite powers of bigraphs

Yoshio Okamoto ; Yota Otachi ; Ryuhei Uehara.

The notion of graph powers is a well-studied topic in graph theory and its applications. In this paper, we investigate a bipartite analogue of graph powers, which we call bipartite powers of bigraphs. We show that the classes of bipartite permutation graphs and interval bigraphs are closed under taking bipartite power. We also show that the problem of recognizing bipartite powers is NP-complete in general.

---

alpha-Labelings and the Structure of Trees with Nonzero alpha-Deficit

Gunnar Brinkmann ; Simon Crevals ; Hadrien Melot ; Leanne Rylands ; Eckhard Steffen.

We present theoretical and computational results on alpha-labelings of trees. The theorems proved in this paper were inspired by the results of a computer investigation of alpha-labelings of all trees with up to 26 vertices, all trees with maximum degree 3 and up to 36 vertices, all trees with maximum degree 4 and up to 32 vertices and all trees with maximum degree 5 and up to 31 vertices. We generalise a criterion for trees to have nonzero alpha-deficit, and prove an unexpected result on the alpha-deficit of trees with a vertex of large degree compared to the order of the tree.

---

The generalized 3-connectivity of Cartesian product graphs

Hengzhe Li ; Xueliang Li ; Yuefang Sun.

The generalized connectivity of a graph, which was introduced by Chartrand et al. in 1984, is a generalization of the concept of vertex connectivity. Let S be a nonempty set of vertices of G, a collection \T-1, T (2), ... , T-r\ of trees in G is said to be internally disjoint trees connecting S if E(T-i) boolean AND E(T-j) - empty set and V (T-i) boolean AND V(T-j) = S for any pair of distinct integers i, j, where 1 <= i, j <= r. For an integer k with 2 <= k <= n, the k-connectivity kappa(k) (G) of G is the greatest positive integer r for which G contains at least r internally disjoint trees connecting S for any set S of k vertices of G. Obviously, kappa(2)(G) = kappa(G) is the connectivity of G. Sabidussi's Theorem showed that kappa(G square H) >= kappa(G) + kappa(H) for any two connected graphs G and H. In this paper, we prove that for any two connected graphs G and H with kappa(3) (G) >= kappa(3) (H), if kappa(G) > kappa(3) (G), then kappa(3) (G square H) >= kappa(3) (G) + kappa(3) (H); if kappa(G) = kappa(3)(G), then kappa(3)(G square H) >= kappa(3)(G) + kappa(3) (H) - 1. Our result could be seen as an extension of Sabidussi's Theorem. Moreover, all the bounds are sharp.

---

Nordhaus-Gaddum Type Results for Total Domination

Michael Henning ; Ernst Joubert ; Justin Southey.

A Nordhaus-Gaddum-type result is a (tight) lower or upper bound on the sum or product of a parameter of a graph and its complement. In this paper we study Nordhaus-Gaddum-type results for total domination. We examine the sum and product of γt(G1) and γt(G2) where G1 ⊕G2 = K(s,s), and γt is the total domination number. We show that the maximum value of the sum of the total domination numbers of G1 and G2 is 2s+4, with equality if and only if G1 = sK2 or G2 = sK2, while the maximum value of the product of the total domination numbers of G1 and G2 is max{8s,⌊(s+6)2/4 ⌋}.

---

On the number of factors in codings of three interval exchange

Petr Ambrož ; Anna Frid ; Zuzana Masáková ; Edita Pelantová.

We consider exchange of three intervals with permutation (3, 2, 1). The aim of this paper is to count the cardinality of the set 3iet (N) of all words of length N which appear as factors in infinite words coding such transformations. We use the strong relation of 3iet words and words coding exchange of two intervals, i.e., Sturmian words. The known asymptotic formula #2iet(N)/N-3 similar to 1/pi(2) for the number of Sturmian factors allows us to find bounds 1/3 pi(2) +o(1) \textless= #3iet(N)N-4 \textless= 2 pi(2) + o(1)

---