Graph Theory

This section of Discrete Mathematics & Theoretical Computer Science seeks high quality articles on structural and algorithmic aspects of graphs and related discrete mathematical models. We particularly seek topics with an intersection between discrete mathematics and computer science. We handle submissions in all areas of finite graph theory.

Editors: Pierre Aboulker ; Jørgen Bang-Jensen ; Bostjan Bresar ; Daniel Goncalves ; Adriana Hansberg ; Frederic Havet ; Michael Anthony Henning ; Tomas Kaiser ; Ken-ichi Kawarabayashi ; Peter Keevash ; Jaehoon Kim ; William Lochet ; Christophe Paul ; Alexandre Pinlou ; Dieter Rautenbach ; Zoltán Szigeti ; Anders Yeo ; Ueverton dos Santos Souza


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 bipartiteRamsey 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 subgraphisomorphic to $G_i$, colored with the $i$th color for some $1\leq i\leq t$. Wecompute 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 completec-partite graph. A c-partite tournament is rich if it is strong, and eachpartite set has at least two vertices. In 1996, Guo and Volkmann characterizedthe structure of all rich c-partite tournaments without (c + 1)-cycles, whichsolved a problem by Bondy. They also put forward a problem that what thestructure 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 aregular mixed graph of given girth with minimum possible order. In this papermixed cages are studied. Upper bounds are obtained by general constructionmethods 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 ofvarious grid graphs, in particular $C_m\square C_n$ for $3 \leq m \leq 6$ andall $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 optimalvalues for $P_m \square C_4$ and $P_m \square C_6$ for $m \geq 3$, $P_4 \squareP_n$ for $n \geq 4$, and $P_5 \square P_n$ for $n \geq 5$. Our method completesan exhaustive case analysis and eliminates cases by combining tools from linearprogramming 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 agraph $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 informationonly, each bear has to guess $g$ colors and he guesses correctly if his hatcolor is included in his guesses. The bears win if at least one bear guessescorrectly 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 thehat chromatic number which has been studied before. We present a surprisingconnection between the hat guessing game and the independence polynomial ofgraphs. This connection allows us to compute the fractional hat chromaticnumber of chordal graphs in polynomial time, to bound fractional hat chromaticnumber by a function of maximum degree of $G$, and to compute the exact valueof $\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 isisomorphic to a subgraph. We extend the definition of homomorphically full tooriented graphs in two different ways. For the first of these, we show thathomomorphically full oriented graphs arise as quasi-transitive orientations ofhomomorphically full graphs. This in turn yields an efficient recognition andconstruction algorithms for these homomorphically full oriented graphs. For thesecond one, we show that the related recognition problem is GI-hard, and thatthe problem of deciding if a graph admits a homomorphically full orientation isNP-complete. In doing so we show the problem of deciding if two given orientedcliques 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 goalis to select a dominating set and Staller's goal is to claim a closedneighborhood 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 Stallerneeds to win. For every positive integer $k$, trees $T$ with $\gamma_{\rmSMB}'(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 fromthe 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 casesexcept when $\ell\ge 4$ and each $n_i$ is even. The simplest formula isobtained when there are at least two odd $n_i$s. If $n_1$ and $n_2$ are the twosmallest 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_{\rmSMB}$ 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 afunction of the twin-widths of $G$ and $H$ and their maximum degrees? It isknown 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 holdfor Cartesian, tensor/direct, corona, rooted, replacement, and zig-zagproducts. For the lexicographical product it is known that the twin-width ofthe product of two graphs is exactly the maximum of the twin-widths of theindividual graphs (Bonnet, Kim, Reinald, Thomassé & Watrigant; IPEC 2021).In contrast, for the modular product we show that no bound can hold. Inaddition, we provide examples showing many of our bounds are tight, and giveimproved 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 connectedgraph 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 ifit 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$ pathsunless $G$ is an odd semi-clique. A graph $G$ is said to be 2-degenerate ifevery subgraph of $G$ has a vertex of degree at most $2$. In this paper, weprove that the edges of any connected 2-degenerate graph $G$ on $n$ verticescan 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 onKneser graphs: Roman domination, total Roman domination, and signed Roman domination. For Kneser graph $K_{n,k}$, we present exact values for Roman dominationnumber $\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 Romandomination 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 isequal to 2, while the upper bound depends on the parity of $n$ and is equal to3 if $n$ is odd, and equal to $5$ if $n$ is even. For graphs of smallerdimensions, 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 thesame color. An edge-colored graph $G^c$ is called \emph{properly colored} ifevery 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 thatevery 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 containedin 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 vertexpair-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 thequestion 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}$ intriangle-free graphs. We also study an opposite version of this question: whatis the maximum number edges/triangles in graphs with double star typerestrictions, which leads us to study two questions related to the extremalnumber of triangles or edges in graphs with degree-sum constraints overadjacent 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 orcycles, 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. Weshow that $c$-Colored $P_\ell$ Deletion and $c$-Colored $C_\ell$ Deletion areNP-hard for each non-trivial combination of $c$ and $\ell$. We then analyze theparameterized complexity of these problems. We extend the notion ofneighborhood diversity to edge-colored graphs and show that both problems arefixed-parameter tractable with respect to the colored neighborhood diversity ofthe input graph. We also provide hardness results to outline the limits ofparameterization by the standard parameter solution size $k$. Finally, weconsider 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 spanof graphs. Using this, we solve the problem of determining the \emph{maximalsafety 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 thispurpose, 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 agraph traversal, where the players may only move with accordance to a specificset of rules, and their goal: visit either all vertices, or all edges. For eachvariant, we show that the solution can be obtained by considering onlyconnected subgraphs of a graph product and the projections to the factors. Wecharacterise graphs in which it is impossible to keep a positive safetydistance at all moments in time. Finally, we present a polynomial timealgorithm 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 thearithmetic mean of the distances from $v$ to all other vertices of $G$. Theproximity $\pi(G)$ and the remoteness $\rho(G)$ of $G$ are the minimum and themaximum of the average distances of the vertices of $G$, respectively. In this paper, we give upper bounds on the remoteness and proximity forgraphs of given order, minimum degree and maximum degree. Our bounds are sharpapart 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 oneof $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 arccolours, and the arc directions of edges and arcs incident with $v$. The groupof all allowed switches is $\Gamma$. Let $k \geq 1$ be a fixed integer and $\Gamma$ a fixed permutation group. Weconsider the problem that takes as input an $(m,n)$-mixed graph $G$ and asks ifthere a sequence of switches at vertices of $G$ with respect to $\Gamma$ sothat the resulting $(m,n)$-mixed graph admits a homomorphism to an$(m,n)$-mixed graph on $k$ vertices. Our main result establishes this problemcan 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 thatfor every graph $G$ with Euler genus $g$ there is a graph $H$ with treewidth atmost 4 and a path $P$ such that $G\subseteq H \boxtimes P \boxtimesK_{\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 framedgraphs. This implies that every $(g,d)$-map graph is contained in $ H \boxtimesP\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\}$. Italso implies that every $(g,1)$-planar graph (that is, graphs that can be drawnin a surface of Euler genus $g$ with at most one crossing per edge) iscontained 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 everyinduced path joining two vertices of $S$ is contained in $S$. The {\emmonophonic convex hull of $S$}, $\langle S \rangle$, is the smallestmonophonically convex set containing $S$. A set $S$ is {\em monophonic convexlyindependent} 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 convexlyindependent set of $G$. We present a characterization of the monophonicconvexly independent sets. Using this result, we show how to determine themonophonic rank of graph classes like bipartite, cactus, triangle-free, andline graphs in polynomial time. Furthermore, we show that this parameter cancomputed in polynomial time for $1$-starlike graphs, i.e., for split graphs,and that its determination is $\NP$-complete for $k$-starlike graphs for anyfixed $k \ge 2$, a subclass of chordal graphs. We also consider this problem onthe 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 graphsand some of its generalizations, in this paper we introduce a naturalgeneralization of de Bruijn graphs (directed and undirected), namely$t$-constrained de Bruijn graphs, where $t$ is a positive integer, and thenstudy the domination number of these graphs. Within the definition of $t$-constrained de Bruijn graphs, de Bruijn andKautz graphs correspond to 1-constrained and 2-constrained de Bruijn graphs,respectively. This generalization inherits many structural properties of deBruijn graphs and may have similar applications in interconnection networks orbioinformatics. We establish upper and lower bounds for the domination number on$t$-constrained de Bruijn graphs both in the directed and in the undirectedcase. These bounds are often very close and in some cases we are able to findthe 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 everyHamiltonian chordal graph is cycle extendible. Here we further explore theconjecture, showing that it fails to hold even when a number of extraconditions are imposed. In particular, we show that Hendry's Conjecture failsfor strongly chordal graphs, graphs with high connectivity, and if we relax thedefinition of "cycle extendible" considerably. We also consider the originalconjecture from a subtree intersection model point of view, showing that aresult 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-disjointtriangles, it suffices to delete at most 2k edges to obtain a triangle-freegraph. The conjecture holds for graphs with small treewidth or small maximumaverage degree, including planar graphs. However, for dense graphs that areneither cliques nor 4-colorable, only asymptotic results are known. Here, weconfirm the conjecture for threshold graphs, i.e. graphs that are both splitgraphs and cographs, and for co-chain graphs with both sides of the same sizedivisible 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 ifthe removal of any $k\le s$ vertices results in a Hamiltonian graph. Given aconnected 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-closedpath $P$ in which all internal vertices have degree 2 such that $P$ is not bothof length 2 and in a $K_3$. For a simple graph $G$, we establish better upperbounds 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 forthe $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 etal. 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 roleof 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 agraph). For certain graphs on $n\geq 6$ vertices, we give the characterizationon 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)\capX_{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-monotonetarget 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 determinedefficiently if $G$ is a tree. We answer their question in the affirmative forthreshold functions $\tau$ satisfying $\tau(u)\in \{ 0,1,d_G(u)\}$ for everyvertex~$u$. For such restricted threshold functions, we give a characterizationof target sets that allows to show that the minimum target set problem remainsNP-hard for planar graphs of maximum degree $3$ but is efficiently solvable forgraphs 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 parametersthat have been key ingredients in the solution of several well-known openproblems. It follows from the definitions that the layered treewidth of a graphis at most its row treewidth plus 1. Moreover, a minor-closed class has boundedlayered treewidth if and only if it has bounded row treewidth. However, it hasbeen open whether row treewidth is bounded by a function of layered treewidth.This paper answers this question in the negative. In particular, for everyinteger $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 computationfor chordal graphs. The neighborhood polynomial of a graph is the generatingfunction of subsets of its vertices that have a common neighbor. We introduce aparameter for chordal graphs called anchor width and an algorithm to computethe neighborhood polynomial which runs in polynomial time if the anchor widthis polynomially bounded. The anchor width is the maximal number of differentsub-cliques of a clique which appear as a common neighborhood. Furthermore westudy the anchor width for chordal graphs and some subclasses such as chordalcomparability graphs and chordal graphs with bounded leafage. the leafage of achordal graphs is the minimum number of leaves in the host tree of a subtreerepresentation. We show that the anchor width of a chordal graph is at most$n^{\ell}$ where $\ell$ denotes the leafage. This shows that for somesubclasses computing the neighborhood polynomial is possible in polynomial timewhile 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 decidewhether there is a dominating set of size at most $k$. In this paper we studythis problem for the Knödel Graph on $n$ vertices using elementary numbertheory techniques. In particular, we show an explicit upper bound for thedomination number of the Knödel Graph on $n$ vertices any time that we canfind 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 topologicalminors 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$, thenthere exists a set of $\mathcal{O}_H(k^3)$ arcs that intersects all immersioncopies of $H$ in $T$. (ii) If in $T$ one cannot find $k$ vertex-disjoint topological minor copiesof $H$, then there exists a set of $\mathcal{O}_H(k\log k)$ vertices thatintersects all topological minor copies of $H$ in $T$. This improves the results of Raymond [DMTCS '18], who proved similarstatements 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 arcset into branchings such that the sizes of any two branchings differ at most byone. For a digraph whose arc set can be partitioned into $k$ branchings, therealways exists an equitable partition into $k$ branchings. In this paper, wepresent two extensions of equitable partitions into branchings in digraphs:those into matching forests in mixed graphs; and into $b$-branchings indigraphs. For matching forests, Király and Yokoi (2022) considered atricriteria equitability based on the sizes of the matching forest, and thematching and branching therein. In contrast to this, we introduce asingle-criterion equitability based on the number of covered vertices, which isplausible in the light of the delta-matroid structure of matching forests.While the existence of this equitable partition can be derived from a lemma inKirá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 equitablepartition always exists. We then derive the integer decomposition property ofthe 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 oneendpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of thebramble is the minimum size of a vertex set that intersects all elements of abramble. Brambles are objects dual to treewidth: As shown by Seymour and Thomas, themaximum order of a bramble in an undirected graph $G$ equals one plus thetreewidth of $G$. However, as shown by Grohe and Marx, brambles of high ordermay necessarily be of exponential size: In a constant-degree $n$-vertexexpander a bramble of order $\Omega(n^{1/2+\delta})$ requires size exponentialin $\Omega(n^{2\delta})$ for any fixed $\delta \in (0,\frac{1}{2}]$. On theother hand, the combination of results of Grohe and Marx and Chekuri andChuzhoy 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 polylogarithmicfactors 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$ iscontained in at most two elements of the bramble (thus the bramble is of sizelinear in its order). Second, we provide a tight upper […]

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 aset $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 lowerbounds on the determining number of Kneser graphs. Moreover, we provide theexact 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 asimple graph of order $n$. The $k$-token graph $F_k(G)$ of $G$ is the graphwhose vertices are the $k$-subsets of $V(G)$, where two vertices are adjacentin $F_k(G)$ whenever their symmetric difference is an edge of $G$. In thispaper we show that if $G$ is a tree, then the connectivity of $F_k(G)$ is equalto 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 forshort) if no two vertices in $G$ have the same set of neighbors in $S$, andeach vertex in $S$ is open-dominated exactly once by $S$. The problem ofdeciding whether or not $G$ has an $OLD_{oind}$-set has important applicationsthat have been reported elsewhere. As the problem is known to be$\mathcal{NP}$-complete, it appears to be notoriously difficult as we show thatits complexity remains the same even for just planar bipartite graphs ofmaximum degree five and girth six, and also for planar subcubic graphs of girthnine. Also, we present characterizations of both $P_4$-tidy graphs and thecomplementary 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, animpressive amount of research has been dedicated to identifying classes ofgraphs that allow Hamiltonian cycles, and to related questions. Thecorresponding decision problem, that asks whether a given graph is Hamiltonian(i.\,e.\ admits a Hamiltonian cycle), is one of Karp's famous NP-completeproblems. 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} frombeing Hamiltonian, if modifying a constant fraction of $n$ edges is necessaryto make $G$ Hamiltonian. We give an explicit deterministic construction of aclass of graphs of bounded degree that are locally Hamiltonian, but (globally)far from being Hamiltonian. Here, \emph{locally Hamiltonian} means that everysubgraph induced by the neighbourhood of a small vertex set appears in someHamiltonian graph. More precisely, we obtain graphs which differ in $\Theta(n)$edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected inthe neighbourhood of $o(n)$ vertices. Our class of graphs yields a class ofhard instances for one-sided error property testers with linear querycomplexity. 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 very few […]

Upward-closed hereditary families in the dominance order

Michael D. Barrus ; Jean A. Guillaume.
The majorization relation orders the degree sequences of simple graphs intoposets called dominance orders. As shown by Ruch and Gutman (1979) and Merris(2002), the degree sequences of threshold and split graphs form upward-closedsets within the dominance orders they belong to, i.e., any degree sequencemajorizing a split or threshold sequence must itself be split or threshold,respectively. Motivated by the fact that threshold graphs and split graphs havecharacterizations 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 presentconditions necessary for a set of graphs to be dominance monotone, and weidentify 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. haveproved 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 shallshow that the extremal digraph on this condition is two classes of digraphsthat 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$ istraceable. 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 propertythat $P$ has a perfect matching. While the maximum cardainality of a minimaldominating set in a graph $G$ is called the upper domination number of $G$,denoted by $\Gamma(G)$, the maximum cardinality of a minimal paired dominatingset 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. Wefocus on the graphs satisfying the equality $\Gamma_{pr}(G)= 2\Gamma(G)$. Wegive characterizations for two special graph classes: bipartite and unicyclicgraphs 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 arestricted girth. In this context, we provide two characterizations: one forgraphs 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 thecharacterization 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\inV([H]_2)$, $uv\in E([H]_2)$ if and only if there is $ f\in F$ such that $u,v\inf$. The treewidth of a graph is an important invariant in structural andalgorithmic graph theory. In this paper, we consider the treewidth of the$2$-section of a linear hypergraph. We will use the minimum degree, maximumdegree, anti-rank and average rank of a linear hypergraph to determine theupper 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 amethod to estimate the bound of treewidth of graph by the parameters of thehypergraph.

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\colonE(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 pairwisedistinct, and the sum of the labels on edges incident to a vertex plus theweight of that vertex is distinct from the sum at every other vertex. In thispaper 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 aninjective edge labeling from $E(G)$ into $\{1,\dotsc,|E(G)|+k\}$ such that thesum of the labels on edges incident to and oriented toward a vertex minus thesum of the labels on edges incident to and oriented away from that vertex isdistinct from the difference of sums at every other vertex. We prove that everygraph 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 addressthis question for the class of {\em split graphs}, that we observe to be thehardest instances for deciding whether the diameter is at most two. We stressthat 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 computethe 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 thecomplexity of diameter computation on {\em subclasses} of split graphs, inorder to better understand the complexity border. Specifically, we consider thesplit graphs with bounded {\em clique-interval number} and their complements,with the former being a natural variation of the concept of interval number forsplit graphs that we introduce in this paper. We first discuss the relationsbetween the clique-interval number and other graph invariants such as theclassic interval number of graphs, the treewidth, the {\em VC-dimension} andthe {\em stabbing number} of a related hypergraph. Then, in part based on theseabove relations, we almost completely settle the complexity of diametercomputation on these subclasses of split graphs: - For the $k$-clique-intervalsplit 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 inaddition a corresponding ordering of the vertices in the […]

Five results on maximizing topological indices in graphs

Stijn Cambie.
In this paper, we prove a collection of results on graphical indices. Wedetermine the extremal graphs attaining the maximal generalized Wiener index(e.g. the hyper-Wiener index) among all graphs with given matching number orindependence number. This generalizes some work of Dankelmann, as well as somework of Chung. We also show alternative proofs for two recents results onmaximizing the Wiener index and external Wiener index by deriving it fromearlier results. We end with proving two conjectures. We prove that the maximumfor the difference of the Wiener index and the eccentricity is attained by thepath if the order $n$ is at least $9$ and that the maximum weighted Szegedindex of graphs of given order is attained by the balanced complete bipartitegraphs.

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 theexistence of polyhedral embeddings of graphs. The emphasis is on cubic graphs.We also describe an efficient algorithm to compute all polyhedral embeddings ofa given cubic graph and constructions for cubic graphs with some specialproperties of their polyhedral embeddings. Some key results are that even cubicgraphs with a polyhedral embedding on the torus can also have polyhedralembeddings in arbitrarily high genus, in fact in a genus {\em close} to thetheoretical maximum for that number of vertices, and that there is no bound onthe 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 graphsdo not have a polyhedral embedding in any genus and that the ratio of thesegraphs 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 thatall vertices appear in the outer region of the drawing and every edge crossesat most one other edge. This paper establishes the local structure ofouter-1-planar graphs by proving that each outer-1-planar graph contains one ofthe seventeen fixed configurations, and the list of those configurations isminimal in the sense that for each fixed configuration there existouter-1-planar graphs containing this configuration that do not contain any ofanother sixteen configurations. There are two interesting applications of thisstructural 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 ofthe degrees of its two end-vertices being at most 9 (resp. 7), and this upperbound is sharp. On the other hand, we show that the list 3-dynamic chromaticnumber of every outer-1-planar graph is at most 6, and this upper bound is bestpossible.

A note on tight cuts in matching-covered graphs

Xiao Zhao ; Sheng Chen.
Edmonds, Lovász, and Pulleyblank showed that if a matching covered graphhas a nontrivial tight cut, then it also has a nontrivial ELP-cut. Carvalho etal. gave a stronger conjecture: if a matching covered graph has a nontrivialtight 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 paperof Carvalho et al. We give a simplified proof of the conjecture, and prove thefollowing result which is slightly stronger than the conjecture: if anontrivial 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 coveredgraphs, 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 asfollows. The input is a graph $G=(V,E)$ where the edge set $E$ is partitionedinto a set $E_r$ of red edges and a set $E_b$ of blue edges. The question iswhether we can delete at most $k$ edges such that $G$ does not contain abicolored $P_3$ as an induced subgraph. Here, a bicolored $P_3$ is a path onthree 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 onbounded-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 apolynomial-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 itadmits a kernel with $ O(k\Delta\min(k,\Delta))$ vertices, where $\Delta$ isthe 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 inmathematical biology as formal models of evolutionary relationships. The(symmetrized) Fitch relation formalizes xenology as the pairs of genesseparated by at least one horizontal transfer event. As a naturalgeneralization, 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 withsubsets 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 caseand then give a characterization of symmetrized Fitch maps in terms ofcompatibility of a certain set of quartets. We show that recognition ofsymmetrized Fitch maps is NP-complete. In the restricted case where$|\varepsilon(x,y)|\leq 1$ the problem becomes polynomial, since such mapscoincide with class of monochromatic Fitch maps whose graph-representationsform 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$ isthe sum of the distances between all unordered pairs of vertices of $G$. Inthis 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 oforder $n$ and minimum degree $\delta$ [M. Kouider, P. Winkler, Mean distanceand minimum degree. J. Graph Theory 25 no. 1 (1997)] can be improvedsignificantly 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 Wienerindex 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 determinea bound on the Wiener index of $C_4$-free graphs of given order, minimum andmaximum 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 whichsome pair of adjacent vertices have the same image. Using a notion of convexityfor oriented graphs, we study those oriented graphs that do not admit suchhomomorphisms. We fully classify those oriented graphs with tree-width $2$ thatdo not admit such homomorphisms and show that it is NP-complete to decide if agraph admits an orientation that does not admit such homomorphisms. We proveanalogous results for $2$-edge-coloured graphs. We apply our results onoriented graphs to provide a new tool in the study of chromatic number oforientations 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 thesum of the distances between all unordered pairs of vertices. We provideasymptotic formulae for the maximum Wiener index of simple triangulations andquadrangulations with given connectivity, as the order increases, and makeconjectures for the extremal triangulations and quadrangulations based oncomputational evidence. If $\overline{\sigma}(v)$ denotes the arithmetic meanof 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 simpletriangulations 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 allnon-isomorphic interval graphs on $n$ vertices with an $O(n^4)$ time delay. Inthis 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 allnon-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 followingconjecture. \noindent\textbf{Conjecture}. {\it Let $D$ be a 2-strongly connected digraphof 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 adigraph $D$ satisfies the conditions of this conjecture and has a pair ofnon-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 transitiveorientation of the edges of its complement graph $\overline{G}$. LBFS$^{+}$ isa variant of the generic Lexicographic Breadth First Search (LBFS), which usesa 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 themaximum length of a cycle of vertex orderings of $G$ obtained via such asequence of LBFS$^{+}$ sweeps. Dusart and Habib conjectured in 2017 thatLexCycle($G$)=2 if $G$ is a cocomparability graph and proved it holds forinterval 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 disjointunion of $P_{2}$ and $P_{3}$. As corollaries, it's applicable for diamond-freecocomparability graphs, cocomparability graphs with girth at least 4, as wellas 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$ usesmore 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 ofsparse graphs. In this note we show two lower bounds on the number of colorsrequired in a $p$-centered coloring. First, we consider monotone classes of graphs whose shallow minors haveaverage degree bounded polynomially in the radius, or equivalently (by a resultof Dvo\v{r}ák and Norin), admitting strongly sublinear separators. Weconstruct such a class such that $p$-centered colorings require a number ofcolors super-polynomial in $p$. This is in contrast with a recent result ofPilipczuk and Siebertz, who established a polynomial upper bound in the specialcase 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$-centeredcolorings with $O(\Delta^{2-1/p} p)$ colors. We show that there are graphs ofmaximum degree $\Delta$ that require $\Omega(\Delta^{2-1/p} p\ln^{-1/p}\Delta)$ colors in any $p$-centered coloring, thus matching theirupper 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 decompositionstarting with an arbitrary edge of $G$. Let $G$ be a graph which has a perfectmatching. 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 thispaper, we characterize cycle-nice claw-free plane graphs. We show that the onlycycle-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 planegraph can be obtained from a graph in the family ${\cal F}$ by a sequence ofthree 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 closedneighborhoods 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 packingnumbers on graph products. In particular we give a complete solution withrespect to some properties of factors in the case of lexicographic and rootedproducts. For Cartesian, strong and direct products, we present several lowerand upper bounds on these parameters.

The agreement distance of unrooted phylogenetic networks

Jonathan Klawitter.
A rearrangement operation makes a small graph-theoretical change to aphylogenetic network to transform it into another one. For unrootedphylogenetic trees and networks, popular rearrangement operations are treebisection and reconnection (TBR) and prune and regraft (PR) (called subtreeprune and regraft (SPR) on trees). Each of these operations induces a metric onthe sets of phylogenetic trees and networks. The TBR-distance between twounrooted phylogenetic trees $T$ and $T'$ can be characterised by a maximumagreement forest, that is, a forest with a minimum number of components thatcovers both $T$ and $T'$ in a certain way. This characterisation hasfacilitated the development of fixed-parameter tractable algorithms andapproximation algorithms. Here, we introduce maximum agreement graphs as ageneralisations of maximum agreement forests for phylogenetic networks. Whilethe agreement distance -- the metric induced by maximum agreement graphs --does not characterise the TBR-distance of two networks, we show that it stillprovides constant-factor bounds on the TBR-distance. We find similar resultsfor 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, theintersection graph class of edge paths on a grid. An EPG graph $G$ is a graphthat 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 theircorresponding paths in $Q$ have a common edge. If the paths in therepresentation have at most $k$ bends, we say that it is a $B_k$-EPGrepresentation. A collection $C$ of sets satisfies the Helly property whenevery sub-collection of $C$ that is pairwise intersecting has at least onecommon 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 representationwhose edge-intersections of paths satisfy the Helly property, so-calledHelly-$B_k$-EPG representation, is in NP, for every $k$ bounded by a polynomialfunction of $|V(G)|$. Moreover, we show that the problem of recognizingHelly-$B_1$-EPG graphs is NP-complete, and it remains NP-complete even whenrestricted 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} askedwhether 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$ forall $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} askedwhether, for a given integer $k\geq 3$, every $k$-regular bipartite graphcontains 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 arejoined 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)$ areadjacent if the intersection of the corresponding $k$-subsets has size $k-1$. Asuper vertex-cut of a connected graph is a set of vertices whose removaldisconnects the graph without isolating a vertex and the super-connectivity isthe size of a minimum super vertex-cut. In this work, we fully determine thesuper-connectivity of the family of Johnson graphs $J(n,k)$ for $n\geq k\geq1$.

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 segmentsreceive different colors. In this paper we show that if $P$ is the pointconfiguration known as the double chain, with $k$ points in the upper convexchain 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 thatthis 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 digraphsis an NP-complete problem. This result was later on extended by Feder et al. toprove that deciding whether a digraph has a circular $p$-colouring isNP-complete for all rational $p>1$. In this paper, we consider the complexityof corresponding decision problems for related notions of fractional colouringsfor digraphs and graphs, including the star dichromatic number, the fractionaldichromatic number and the circular vertex arboricity. We prove the followingresults: Deciding if the star dichromatic number of a digraph is at most $p$ isNP-complete for every rational $p>1$. Deciding if the fractional dichromatic number of a digraph is at most $p$ isNP-complete for every $p>1, p \neq 2$. Deciding if the circular vertex arboricity of a graph is at most $p$ isNP-complete for every rational $p>1$. To show these results, different techniques are required in each case. Inorder to prove the first result, we relate the star dichromatic number to a newnotion of homomorphisms between digraphs, called circular homomorphisms, whichmight be of independent interest. We provide a classification of thecomputational complexities of the corresponding homomorphism colouring problemssimilar 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 listassignment $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 ifthe 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$-choosablewhere $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 aloose 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 ofconsecutive edges intersects on a single vertex, while all other pairs aredisjoint. 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 amonochromatic copy of $P_\ell^{(k)}$. In this paper we are mostly interested inconstructive upper bounds on $R(P_\ell^{(k)};r)$, meaning that on the cost ofpossibly enlarging the order of the complete hypergraph, we would like toefficiently find a monochromatic copy of $P_\ell^{(k)}$ in every coloring. Inparticular, 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 analgorithm such that for every $r$-edge-coloring of the edges of $K_n^{(k)}$, itfinds a monochromatic copy of $P_\ell^{(k)}$ in time at most $cn^k$. We alsoprove 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 uniquelyembeddable on the sphere. On the other hand, it has many inequivalentembeddings 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 betweeninequivalent embeddings of $G$ on each surface and some subgraphs of the dualof $G$ embedded on the sphere. These results enable us to give explicit boundsfor the number of inequivalent embeddings of $G$ on each surface, and proposeeffective 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 generaland for many restricted cases. One way to restrict instances of $k$-SAT is tolimit the number of times a variable can be occurred. It was shown that for aninstance of 4-SAT with the property that every variable appears in exactly 4clauses (2 times negated and 2 times not negated), determining whether there isan assignment for variables such that every clause contains exactly two truevariables and two false variables is $\mathbf{NP}$-complete. In this work, weshow that deciding the satisfiability of 3-SAT with the property that everyvariable appears in exactly four clauses (two times negated and two times notnegated), and each clause contains at least two distinct variables is $\mathbf{NP} $-complete. We call this problem $(2/2/3)$-SAT. For an $r$-regulargraph $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 thatfor every $r\geq 3$, this problem is $ \mathbf{NP} $-complete. Among otherresults, we study the relationship between 1-perfect codes and the incidencecoloring of graphs and as another application of our complexity results, weprove that for a given cubic graph $G$ deciding whether $G$ is 4-incidencecolorable 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 withlabel $a$ differs by at most $1$ from the number of vertices with label $b$ andthe 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 analogousproblem for hypertrees, that is, connected hypergraphs without cycles. The mainresults of their work are that every $k$-uniform hypertree is $k$-cordial forevery $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 thisarticle, we confirm the conjecture of Cichacz et al. and make a step further byproving 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 thepresence of edge failures. $k$-restricted edge-connectivity is one of therefined indicators for fault tolerance of large networks. Matching preclusionand conditional matching preclusion are two important measures for therobustness of networks in edge fault scenario. In this paper, we show that theDCell 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$, andsuper-$\lambda_3$ for $k\geq4$ and $n\geq3$. Moreover, as an application of$k$-restricted edge-connectivity, we study the matching preclusion number andconditional matching preclusion number, and characterize the correspondingoptimal solutions of $D_{k,n}$. In particular, we have shown that $D_{1,n}$ isisomorphic 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 tomake a given coloured graph monochromatic in the one-player combinatorial gameFlood-It has been studied extensively from an algorithmic point of view, butbasic questions about the maximum number of moves that might be required in theworst case remain unanswered. We begin a systematic investigation of suchquestions, with the goal of determining, for a given graph, the maximum numberof moves that may be required, taken over all possible colourings. We giveseveral upper and lower bounds on this quantity for arbitrary graphs and showthat all of the bounds are tight for trees; we also investigate how much theupper bounds can be improved if we restrict our attention to graphs with higheredge-density.

On almost hypohamiltonian graphs

Jan Goedgebeur ; Carol T. Zamfirescu.
A graph $G$ is almost hypohamiltonian (a.h.) if $G$ is non-hamiltonian, thereexists a vertex $w$ in $G$ such that $G - w$ is non-hamiltonian, and $G - v$ ishamiltonian 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. Herewe solve this problem. To this end, we present a specialised algorithm whichgenerates complete sets of a.h. graphs for various orders. Furthermore, we showthat the smallest cubic a.h. graphs have order 26. We provide a lower bound forthe order of the smallest planar a.h. graph and improve the upper bound for theorder of the smallest planar a.h. graph containing a cubic vertex. We alsodetermine the smallest planar a.h. graphs of girth 5, both in the general andcubic case. Finally, we extend a result of Steffen on snarks and improve twobounds on longest paths and longest cycles in polyhedral graphs due toJooyandeh, 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 twovertices of $S$ lie in $S$. The cardinality $con(G)$ of a maximum proper convexset $S$ of $G$ is the $\textit{convexity number}$ of $G$. The$\textit{complementary prism}$ $G\overline{G}$ of a graph $G$ arises from thedisjoint union of the graph $G$ and $\overline{G}$ by adding the edges of aperfect matching between the corresponding vertices of $G$ and $\overline{G}$.In this work, we we prove that the decision problem related to the convexitynumber is NP-complete even restricted to complementary prisms, we determine$con(G\overline{G})$ when $G$ is disconnected or $G$ is a cograph, and wepresent 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 ofclassical domination where selected vertices may have different dominationpowers. 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 multipackingis 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). Naturallymp(G) $\leq \gamma_b(G)$. Earlier results by Farber and by Lubiw show thatbroadcast and multipacking numbers are equal for strongly chordal graphs. Inthis paper, we show that all large grids (height at least 4 and width at least7), which are far from being chordal, have their broadcast and multipackingnumbers equal.

The agreement distance of rooted phylogenetic networks

Jonathan Klawitter.
The minimal number of rooted subtree prune and regraft (rSPR) operationsneeded to transform one phylogenetic tree into another one induces a metric onphylogenetic trees - the rSPR-distance. The rSPR-distance between twophylogenetic trees $T$ and $T'$ can be characterised by a maximum agreementforest; a forest with a minimum number of components that covers both $T$ and$T'$. The rSPR operation has recently been generalised to phylogenetic networkswith, among others, the subnetwork prune and regraft (SNPR) operation. Here, weintroduce maximum agreement graphs as an explicit representations ofdifferences of two phylogenetic networks, thus generalising maximum agreementforests. We show that maximum agreement graphs induce a metric on phylogeneticnetworks - the agreement distance. While this metric does not characterise thedistances induced by SNPR and other generalisations of rSPR, we prove that itstill 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 appearingon edges incident with $v$. The palette index $\check s(G)$ of $G$ is theminimum 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 onepart have degree $a$ and all vertices in the other part have degree $b$. Weconjecture that if $G$ is $(a,b)$-biregular, then $\check{s}(G)\leq1+\max\{a,b\}$, and we prove that this conjecture holds for several families of$(a,b)$-biregular graphs. Additionally, we characterize the graphs whosepalette 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 atleast $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)$, weprovide some new lower bounds based on exhaustive searches, and then obtainseveral new upper bounds using computer algorithms for the construction ofwitnesses, and for the verification of their correctness. We also present thefirst examples of reasonably small order for $k = 4$ and $g > 5$. Inparticular, 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 treemetric. 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 shortestpaths connecting these vertices. A geodesic triangle $\bigtriangleup(x,y,z)$ iscalled $\delta$-slim if for any vertex $u\in V$ on any side $P(x,y)$ thedistance from $u$ to $P(x,z) \cup P(y,z)$ is at most $\delta$, i.e. each pathis 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 iscalled the slimness of $G$. In this paper, using the layering partitiontechnique, 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 showthat the slimness of every 4-chordal graph is at most 2 and characterize those4-chordal graphs for which the slimness of every of its induced subgraph is atmost 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 smallestinteger $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, areintroduced 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 almostarbitrary. The $3$-$\chi_{\rho}$-critical graphs are characterized, and$4$-$\chi_{\rho}$-critical graphs are characterized in the case when theycontain 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}$-criticalcaterpillar exists if and only if $k\le 7$. Cartesian products are alsoconsidered and in particular it is proved that if $G$ and $H$ arevertex-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 smallestinteger $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 distancegreater than $i$. In this paper, we consider the packing chromatic number ofseveral families of Sierpinski-type graphs. We establish the packing chromaticnumbers 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 oforder four. Furthermore, we prove that the packing chromatic number in thefamily 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$ andtotal 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 thatevery forest $F$ with order $n$, no isolated vertex, and total dominationnumber $\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 aperfect matching is $E(m, n)$-{\it extendable}, if for any two sets of disjointindependent edges $M$ and $N$ with $|M| = m$ and $|N|= n$, there is a perfectmatching $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 bindingnumber 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)\geq4/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 thatthe binding number and toughness conditions for the existence of the generalmatching extension properties are almost same as that for the existence ofperfect 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 incirculant graphs of type $C_n(1,2, \ldots, r)$, which can also be viewed aspower graphs of cycles. Recently, Ghebleh and Niepel (2013) consideredidentification and location-domination in the circulant graphs $C_n(1,3)$. Theyshowed 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 beincreased 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 isattained for most of the lengths $n$ and conjectured that in the rest of thecases the lower bound can improved by one. This conjecture is also proved inthe 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 toidentification and location-domination, also manages to take advantage of theglobal 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 verticesinto 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 ofneighbors 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 afunction $ \ell :V(G) \rightarrow \mathbb{N}$, such that for every two adjacentvertices $ v $ and $ u$ of $ G $, $ \sum_{w \sim v}\ell(w)\neq \sum_{w \simu}\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 $ suchthat $ G $ has a lucky labeling $ \ell :V(G) \rightarrow \mathbb{N}_k$. It wasconjectured 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-regulargraph $G$. In this work, we prove this conjecture. Among other results, we givean 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 tobe \emph{kernel perfect} (KP for short) (\emph{critical kernel imperfect} (CKIfor short) resp.) if the digraph has a kernel (does not have a kernel resp.).The unique CKI-tournament is $\overrightarrow{C}_3$ and the uniqueKP-tournaments are the transitive tournaments, however bipartite tournamentsare KP. In this paper we characterize the CKI- and KP-digraphs for thefollowing families of digraphs: locally in-/out-semicomplete, asymmetricarc-locally in-/out-semicomplete, asymmetric $3$-quasi-transitive andasymmetric $3$-anti-quasi-transitive $TT_3$-free and we state that the problemof determining whether a digraph of one of these families is CKI is polynomial,giving a solution to a problem closely related to the following conjectureposted by Bang-Jensen in 1998: the kernel problem is polynomially solvable forlocally 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$ islocally-injective if, for every $v \in V(G)$, it is injective when restrictedto some combination of the in-neighbourhood and out-neighbourhood of $v$. Twoof the possible definitions of local-injectivity are examined. In each case itis shown that the associated homomorphism problem is NP-complete when $H$ is areflexive tournament on three or more vertices with a loop at every vertex, andsolvable in polynomial time when $H$ is a reflexive tournament on two or fewervertices.

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-completeproblem even if $G$ is 2-connected, planar, and subcubic. In this work wepresent results on matching-decyclability in the following classes: Hamiltoniansubcubic graphs, chordal graphs, and distance-hereditary graphs. In Hamiltoniansubcubic graphs we show that deciding matching-decyclability is NP-completeeven if there are exactly two vertices of degree two. For chordal anddistance-hereditary graphs, we present characterizations ofmatching-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 aregraphs with all maximal independent sets of the same size. The extent to whicha 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 maximalindependent set in $G$. While the well-covered graphs are exactly the graphs ofindependence gap zero, we investigate in this paper graphs of independence gapone, which we also call almost well-covered graphs. Previous works due toFinbow et al. (1994) and Barbosa et al. (2013) have implications for thestructure 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 showthat every graph in this class has at most two vertices each of which isadjacent to exactly $2$ leaves. We give efficiently testable characterizationsof almost well-covered graphs of girth at least $6$ having exactly one orexactly two such vertices. Building on these results, we develop apolynomial-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 atransmission antenna network. In this paper, we study a limited version of thisstructure, that was proposed as a common framework for both broadcast andclassical domination. In this limited version, the broadcast function is upperbounded by an integer $k$ and the minimum cost of such function is thedominating $k$-broadcast number. Our main result is a unified upper bound onthis parameter for any value of $k$ in general graphs, in terms of both $k$ andthe order of the graph. We also study the computational complexity of theassociated 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 sizeamong all connected subgraphs whose vertex sets contain $S$. Let $n$ and $k$ betwo 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\inV(G)\}$. In this paper, we investigate the Steiner distance and Steiner$k$-diameter of Cartesian and lexicographical product graphs. Also, we studythe 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 theedge 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 numberof moves, depending on $b$, in which Maker can win in each of the two standardgraph 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 twoimportant domination parameters, namely the domination number, $\gamma(G)$, andthe total domination number, $\gamma_t(G)$. A set $S$ of vertices in $G$ is asemitotal dominating set of $G$ if it is a dominating set of $G$ and everyvertex in S is within distance $2$ of another vertex of $S$. The semitotaldomination number, $\gamma_{t2}(G)$, is the minimum cardinality of a semitotaldominating 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 dominationnumber of trees and we characterize the extremal trees. In addition, wecharacterize 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 orincident 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 setsof $G$. Any mixed dominating set with the cardinality of $\gamma_m(G)$ iscalled a minimum mixed dominating set. The mixed domination set (MDS) problemis to find a minimum mixed dominating set for a graph $G$ and is known to be anNP-complete problem. In this paper, we present a novel approach to find all ofthe mixed dominating sets, called the AMDS problem, of a graph with boundedtree-width $tw$. Our new technique of assigning power values to edges andvertices, and combining with dynamic programming, leads to a fixed-parameteralgorithm of time $O(3^{tw^{2}}\times tw^2 \times |V|)$. This shows that MDS isfixed-parameter tractable with respect to tree-width. In addition, wetheoretically 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 everyAbelian 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\inN(v)}f(xv)$ for each edge $uv\in E(G)$ is called the \textit{group twinchromatic index} of $G$ and denoted by $\chi'_g(G)$. This graph invariant isrelated to a few well-known problems in the field of neighbor distinguishinggraph colorings. We conjecture that $\chi'_g(G)\leq \Delta(G)+3$ for all graphswithout isolated edges, where $\Delta(G)$ is the maximum degree of $G$, andprovide an infinite family of connected graph (trees) for which the equalityholds. We prove that this conjecture is valid for all trees, and then applythis 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 knownupper 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 onits largest and smallest elements, length, and sum. This bound generalizes aresult 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 totaldomination number, respectively, of a graph $G$ with no isolated vertices. Itis well-known that $\gamma_t(G) \leq 2\gamma(G)$. We provide a characterizationof 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 arecolored the same. The graph $G$ is rainbow-connected if there is a rainbow pathbetween every pair of vertices. If there is a rainbow shortest path betweenevery pair of vertices, the graph $G$ is strongly rainbow-connected. Theminimum number of colors needed to make $G$ rainbow-connected is known as therainbow connection number of $G$, and is denoted by $\text{rc}(G)$. Similarly,the minimum number of colors needed to make $G$ strongly rainbow-connected isknown 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 subclassof chordal graphs. Furthermore, there exists no polynomial-time algorithm forapproximating the strong rainbow connection number of an $n$-vertex split graphwith a factor of $n^{1/2-\epsilon}$ for any $\epsilon > 0$ unless P = NP. Wethen turn our attention to block graphs, which also form a subclass of chordalgraphs. We determine the strong rainbow connection number of block graphs, andshow it can be computed in linear time. Finally, we provide a polynomial-timecharacterization of bridgeless block graphs with rainbow connection number atmost 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 ifthere exists an S-edge-weighting $w : E(G) \rightarrow S$ such that any twoadjacent vertices have different sums of incident edge-weights. In this paperwe characterise all bridgeless bipartite graphs and all trees without the$\{0,1\}$-property. In particular this problem belongs to P for these graphswhile 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 graphssuch that there exists a constant $c=c(\mathcal{H})$ satisfying $\gamma (G)\leqc$ for every connected $\mathcal{H}$-free graph $G$, where $\gamma (G)$ is thedomination 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 antimagiclabelling. 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 antimagiclabelling, where only adjacent vertices must be distinguished. Both sets ofauthors conjectured that any connected graph other than $K_2$ admits a localantimagic labelling. We prove this latter conjecture using the probabilisticmethod. Thus the parameter of local antimagic chromatic number, introduced byArumugam 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 ofthe weakly threshold sequences. The weakly threshold graphs properly includethe threshold graphs and satisfy pleasing extensions of many properties ofthreshold graphs. We demonstrate a majorization property of weakly thresholdsequences and an iterative construction algorithm for weakly threshold graphs,as well as a forbidden induced subgraph characterization. We conclude byexactly 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 meetsprecisely once. Conway's Thrackle Conjecture asserts that a thrackle drawing ofa graph on the plane cannot have more edges than vertices. We prove theConjecture 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 adetailed 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 randomfamily of sets. Such structures, which are derived from intersections of sets,appear in a natural manner in many applications. In this article we study theproblem of finding a Hamilton cycle in a random intersection graph. To this endwe analyse a classical algorithm for finding Hamilton cycles in random graphs(algorithm HAM) and study its efficiency on graphs from a family of randomintersection graphs (denoted here by G(n,m,p)). We prove that the thresholdfunction for the property of HAM constructing a Hamilton cycle in G(n,m,p) isthe same as the threshold function for the minimum degree at least two. Untilnow, known algorithms for finding Hamilton cycles in G(n,m,p) were designed towork in very small ranges of parameters and, unlike HAM, used the structure ofthe 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 beassigned different colours. A homomorphism model that extends the ideas ofSherk for the case $k=2$ is described. Dichotomy theorems for the complexity ofthe 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 whethera poset can be (weakly) embedded into a small Boolean lattice, or to a fewconsecutive levels of a Boolean lattice, are NP-complete, answering a questionof Griggs and of Patkos. As an equivalent reformulation of one of theseproblems, we also derive that it is NP-complete to decide whether a given graphcan 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 ofcombinatorial structures and has been mostly studied in the setting ofundirected 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 thatcontain $H$ as a strong minor (resp. butterfly minor, topological minor) hasthe vertex-Erdős-Pósa property in the class of tournaments. We also provethat if $H$ is a strongly-connected directed graph, the class of directedgraphs containing $H$ as an immersion has the edge-Erdős-Pósa property inthe 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 thediffusion game. Chips are initially assigned to vertices of a graph. At everystep, all vertices simultaneously send one chip to each neighbour with fewerchips. As the dynamics of the parallel chip-firing game occur on a finite setthe process is inherently periodic. However the diffusion game is not obviouslyperiodic: even if $2|E(G)|$ chips are assigned to vertices of graph G, theremay exist time steps where some vertices have a negative number of chips. Weinvestigate the process, prove periodicity for a number of graph classes, andpose 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 Raspaudproposed a weaker conjecture: For every bridgeless cubic graph $G$, there arethree perfect matchings $M_1$, $M_2$, and $M_3$ such that $M_1\cap M_2 \capM_3=\emptyset$. We call the property specified in this conjecture the threematching intersection property (and 3PM property for short). We study thisproperty on matching covered graphs. The main results are a necessary andsufficient condition and its applications to characterization of specialgraphs, 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 withfinding a maximal distance-$k$ matching of minimum cardinality or minimumweight in a given graph. We introduce the class of $k$-equimatchable graphswhich is an edge analogue of $k$-equipackable graphs. We prove that therecognition of $k$-equimatchable graphs is co-NP-complete for any fixed $k \ge2$. We provide a simple characterization for the class of strongly chordalgraphs with equal $k$-packing and $k$-domination numbers. We also prove thatfor any fixed integer $\ell \ge 1$ the problem of finding a minimum weightmaximal distance-$2\ell$ matching and the problem of finding a minimum weight$(2 \ell - 1)$-independent dominating set cannot be approximated in polynomialtime in chordal graphs within a factor of $\delta \ln |V(G)|$ unless$\mathrm{P} = \mathrm{NP}$, where $\delta$ is a fixed constant (therebyimproving the NP-hardness result of Chang for the independent domination case).Finally, we show the NP-hardness of the minimum maximal induced matching andindependent 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 VPTgraph (i.e. the vertex intersection graph) of the paths P, and EPT(P) is theEPT graph (i.e. the edge intersection graph) of P. These graphs have beenextensively studied in the literature. Given two (edge) intersecting paths in agraph, their split vertices is the set of vertices having degree at least 3 intheir union. A pair of (edge) intersecting paths is termed non-splitting ifthey do not have split vertices (namely if their union is a path). We definethe graph ENPT(P) of edge intersecting non-splitting paths of a tree, termedthe ENPT graph, as the graph having a vertex for each path in P, and an edgebetween every pair of vertices representing two paths that are bothedge-intersecting and non-splitting. A graph G is an ENPT graph if there is atree T and a set of paths P of T such that G=ENPT(P), and we say that isa 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 bythe 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, wedefine two problems HamiltonianPairRec, P3-HamiltonianPairRec and characterizethe representations of ENPT holes that satisfy (P1), (P2), (P3). In this work, we continue our work by relaxing these three assumptions one byone. We characterize the representations of ENPT […]

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 bipartitedigraph to be hamiltonian. Let $D$ be a balanced bipartite digraph and $x,y$ bedistinct 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. Inthis 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 orderingof vertices, if the endpoints of the two edges do not alternate in theordering. 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 ofthe circular orderings. This notion is introduced by Loeb and West in theirrecent paper. In this article, we consider two subclasses of planar graphs,namely $2$-outerplanar graphs and series-parallel graphs. A $2$-outerplanargraph has a planar embedding such that the subgraph obtained by removal of thevertices 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 aseries-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-constrainedpath-cycle decompositions, that is, partitions of the edge set of a graph intopaths and cycles of a given minimum length. Our main contribution is thecharacterization of the class of all triangle-free graphs with odd distance atleast $3$ that admit a path-cycle decomposition with elements of length atleast $4$. As a consequence, it follows that Gallai's conjecture on pathdecomposition 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 thatthe 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 anextremal graph and $M$ is a nice perfect matching. We obtain an equivalentcondition for the nice perfect matchings of $G$ and establish a one-to-onecorrespondence 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 extremalgraphs 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 thecomplete 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 cutsetthat has unbounded rank-width. In general, even-hole-free graphs have unboundedrank-width, because chordal graphs are even-hole-free. A.A. da Silva, A. Silvaand C. Linhares-Sales (2010) showed that planar even-hole-free graphs havebounded rank-width, and N.K. Le (2016) showed that even-hole-free graphs withno star cutset have bounded rank-width. A natural question is to ask, whethereven-hole-free graphs with no clique cutsets have bounded rank-width. Ourresult gives a negative answer. Hence we cannot apply Courcelle and Makowsky'smeta-theorem which would provide efficient algorithms for a large number ofproblems, including the maximum independent set problem, whose complexityremains 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 bootstrappercolation) is a dynamic process on a graph where vertices change color fromwhite 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 thatthe irreversible $k$-threshold process starting with $S$ black eventuallychanges all vertices of $G$ to black. We show that deciding the existence of anirreversible 2-conversion set of a given size is NP-complete, even for graphsof 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 anirreversible 2-conversion set can be computed in polynomial time. Moreover, wefind 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 areof the same size. The class of well-dominated graphs forms a subclass of thewell studied class of well-covered graphs. While the recognition problem forthe class of well-covered graphs is known to be co-NP-complete, the recognitioncomplexity of well-dominated graphs is open. In this paper we introduce the notion of an irreducible dominating set, avariant of dominating set generalizing both minimal dominating sets and minimaltotal dominating sets. Based on this notion, we characterize the family ofminimal dominating sets in a lexicographic product of two graphs and derive acharacterization of the well-dominated lexicographic product graphs. As a sideresult motivated by this study, we give a polynomially testablecharacterization of well-dominated graphs with domination number two, and show,more generally, that well-dominated graphs can be recognized in polynomial timein any class of graphs with bounded domination number. Our results include acharacterization of dominating sets in lexicographic product graphs, whichgeneralizes the expression for the domination number of such graphs followingfrom 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 asthe second half. An edge-coloring of a graph is repetition-free ornonrepetitive 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-coloringis called its Thue edge-chromatic number. We improve on the best known general upper bound of $4\Delta-4$ for the Thueedge-chromatic number of trees of maximum degree $\Delta$ due to Alon,Grytczuk, Ha{\l}uszczak and Riordan (2002) by providing a simple nonrepetitiveedge-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 filamentgraphs, the overlap graphs of subtrees of a star are cocomparability graphs,and the overlap graphs of subtrees of a caterpillar are interval filamentgraphs. In this paper, we show the equivalence of many more classes of subtreeoverlap and subtree filament graphs, and equate them to classes of complementsof cochordal-mixed graphs. Our results generalize the previously known resultsmentioned 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 thegraph classes Edge-Intersecting and Non-Splitting Paths in a Tree ENPT, and ina Grid (ENPG). It was shown that ENPG contains an infinite hierarchy ofsubclasses 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. Weshow 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 characterizethe split graphs and co-bipartite graphs that are one bend ENPG. We prove thatthe recognition problem of one bend ENPG split graphs is NP-complete even in avery restricted subfamily of split graphs. Last we provide a linear timerecognition 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 andWiener 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 areidentified. Based on these results, further relation on the quotients betweenthe (revised) Szeged index and the Wiener index are studied. Sharp lower boundon $Sz(G)/W(G)$ is determined for all connected graphs each of which containsat least one non-complete block. As well the connected graph with the secondsmallest value on $Sz^*(G)/W(G)$ is identified for $G$ containing at least onecycle.

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 vertexof $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 themaximum cardinality of a $2$-independent set in $G$. Chellali and Meddah [{\itTrees with equal $2$-domination and $2$-independence numbers,} DiscussionesMathematicae Graph Theory 32 (2012), 263--270] provided a constructivecharacterization of trees with equal $2$-domination and $2$-independencenumbers. Their characterization is in terms of global properties of a tree, andinvolves properties of minimum $2$-dominating and maximum $2$-independent setsin the tree at each stage of the construction. We provide a constructivecharacterization that relies only on local properties of the tree at each stageof 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 graphinvariant whose study started two decades ago. The distinguishing number $D(G)$is the least integer $d$ such that $G$ has a $d$-distinguishing coloring. Adistinguishing $d$-coloring is a coloring $c:V(G)\rightarrow\{1,...,d\}$invariant only under the trivial automorphism. In this paper, we introduce agame variant of the distinguishing number. The distinguishing game is a gamewith two players, the Gentle and the Rascal, with antagonist goals. This gameis 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 ifthe coloring is distinguishing and the Rascal wins otherwise. This game leadsto define two new invariants for a graph $G$, which are the minimum numbers ofcolors needed to ensure that the Gentle has a winning strategy, depending onwho starts. These invariants could be infinite, thus we start by givingsufficient conditions to have infinite game distinguishing numbers. We alsoshow that for graphs with cyclic automorphisms group of prime odd order, bothgame invariants are finite. After that, we define a class of graphs, theinvolutive graphs, for which the game distinguishing number can bequadratically bounded above by the classical distinguishing number. Thedefinition of this class is closely related to imprimitive actions whose […]

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 areorientations where the outdegree of each vertex is prescribed by the value of agiven function $\alpha$. The set of $\alpha$-orientations of a plane graph hasa natural distributive lattice structure. The moves of the up-down Markov chainon this distributive lattice corresponds to reversals of directed facial cyclesin the $\alpha$-orientation. We have a positive and several negative resultsregarding the mixing time of such Markov chains. A 2-orientation of a plane quadrangulation is an orientation where everyinner vertex has outdegree 2. We show that there is a class of planequadrangulations such that the up-down Markov chain on the 2-orientations ofthese quadrangulations is slowly mixing. On the other hand the chain is rapidlymixing on 2-orientations of quadrangulations with maximum degree at most 4. Regarding examples for slow mixing we also revisit the case of 3-orientationsof triangulations which has been studied before by Miracle et al.. Our examplesfor slow mixing are simpler and have a smaller maximum degree, Finally wepresent the first example of a function $\alpha$ and a class of planetriangulations of constant maximum degree such that the up-down Markov chain onthe $\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 beextended to a Hamiltonian cycle. A positive answer is known for perfectmatchings, but the general case has been resolved only for matchings of linearsize. In this paper we show that there is a quadratic function $q(n)$ such thatevery matching in the $n$-dimensional hypercube of size at most $q(n)$ may beextended 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 ofvertices whose open neighborhoods partition its vertex set. We characterizethose graphs $G$ for which the Cartesian product $G \Box H$ is an efficientopen domination graph when $H$ is a complete graph of order at least 3 or acomplete bipartite graph. The characterization is based on the existence of acertain type of weak partition of $V(G)$. For the class of trees when $H$ iscomplete of order at least 3, the characterization is constructive. Inaddition, a special type of efficient open domination graph is characterizedamong 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 inseveral problems related to overcoming failures, since they frequently havesome common approaches around the notion of majorities, for instance toconsensus problems, diagnosis problems or voting systems. We introduce hereopen $k$-monopolies in graphs which are closely related to different parametersin graphs. Given a graph $G=(V,E)$ and $X\subseteq V$, if $\delta_X(v)$ is thenumber of neighbors $v$ has in $X$, $k$ is an integer and $t$ is a positiveinteger, then we establish in this article a connection between the followingthree 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\inV$. In this article we prove that the problem of computing the minimumcardinality of an open $0$-monopoly in a graph is NP-complete even restrictedto bipartite or chordal graphs. In addition we present some general bounds forthe 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 ofmaximum degree $\Delta\ge3$ is bounded from above by\[\frac{(\Delta-1)^m-1}{\Delta-2}+2^m+1,\] which improves the best known boundby 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 ⌊log2$n$⌋$-1$. For some special configurations of point sets, we give the exact answer. We also consider some restricted variants of this problem.

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 complexity of $P$4-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.

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.

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.

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.

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).

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.

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.

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.

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.

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.

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.

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).

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.

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

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).

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.

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.

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)