vol. 24, no 2


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

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

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.

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

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

6. 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$.

7. On Dualization over Distributive Lattices

Khaled Elbassioni.
Given a partially order set (poset) $P$, and a pair of families of ideals$\mathcal{I}$ and filters $\mathcal{F}$ in $P$ such that each pair $(I,F)\in\mathcal{I}\times\mathcal{F}$ has a non-empty intersection, the dualizationproblem over $P$ is to check whether there is an ideal $X$ in $P$ whichintersects every member of $\mathcal{F}$ and does not contain any member of$\mathcal{I}$. Equivalently, the problem is to check for a distributive lattice$L=L(P)$, given by the poset $P$ of its set of joint-irreducibles, and twogiven antichains $\mathcal{A},\mathcal{B}\subseteq L$ such that no$a\in\mathcal{A}$ is dominated by any $b\in\mathcal{B}$, whether $\mathcal{A}$and $\mathcal{B}$ cover (by domination) the entire lattice. We show that theproblem can be solved in quasi-polynomial time in the sizes of $P$,$\mathcal{A}$ and $\mathcal{B}$, thus answering an open question in Babin andKuznetsov (2017). As an application, we show that minimal infrequent closedsets of attributes in a rational database, with respect to a given implicationbase of maximum premise size of one, can be enumerated in incrementalquasi-polynomial time.

8. Approximability results for the $p$-centdian and the converse centdian problems

Yen Hung Chen.
Given an undirected graph $G=(V,E)$ with a nonnegative edge length functionand an integer $p$, $0 < p < |V|$, the $p$-centdian problem is to find $p$vertices (called the {\it centdian set}) of $V$ such that the {\iteccentricity} plus {\it median-distance} is minimized, in which the {\iteccentricity} is the maximum (length) distance of all vertices to their nearest{\it centdian set} and the {\it median-distance} is the total (length) distanceof all vertices to their nearest {\it centdian set}. The {\it eccentricity}plus {\it median-distance} is called the {\it centdian-distance}. The purposeof the $p$-centdian problem is to find $p$ open facilities (servers) whichsatisfy the quality-of-service of the minimum total distance ({\itmedian-distance}) and the maximum distance ({\it eccentricity}) to theirservice customers, simultaneously. If we converse the two criteria, that isgiven the bound of the {\it centdian-distance} and the objective function is tominimize the cardinality of the {\it centdian set}, this problem is called theconverse centdian problem. In this paper, we prove the $p$-centdian problem isNP-Complete. Then we design the first non-trivial brute force exact algorithmsfor the $p$-centdian problem and the converse centdian problem, respectively.Finally, we design two approximation algorithms for both problems.

9. Token Swapping on Trees

Ahmad Biniaz ; Kshitij Jain ; Anna Lubiw ; Zuzana Masárová ; Tillmann Miltzow ; Debajyoti Mondal ; Anurag Murty Naredla ; Josef Tkadlec ; Alexi Turcotte.
The input to the token swapping problem is a graph with vertices $v_1, v_2,\ldots, v_n$, and $n$ tokens with labels $1, 2, \ldots, n$, one on each vertex.The goal is to get token $i$ to vertex $v_i$ for all $i= 1, \ldots, n$ using aminimum number of swaps, where a swap exchanges the tokens on the endpoints ofan edge. We present some results about token swapping on a tree, also known as"sorting with a transposition tree": 1. An optimum swap sequence may need to perform a swap on a leaf vertex thathas the correct token (a "happy leaf"), disproving a conjecture of Vaughan. 2. Any algorithm that fixes happy leaves -- as all known approximationalgorithms for the problem do -- has approximation factor at least $4/3$.Furthermore, the two best-known 2-approximation algorithms have approximationfactor exactly 2. 3. A generalized problem -- weighted coloured token swapping -- isNP-complete on trees, even when they are restricted to be subdivided stars, butsolvable in polynomial time on paths and stars. In this version, tokens andvertices have colours, and colours have weights. The goal is to get every tokento a vertex of the same colour, and the cost of a swap is the sum of theweights of the two tokens involved.

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

11. A heuristic technique for decomposing multisets of non-negative integers according to the Minkowski sum

Luciano Margara.
We study the following problem. Given a multiset $M$ of non-negativeintegers, decide whether there exist and, in the positive case, compute twonon-trivial multisets whose Minkowski sum is equal to $M$. The Minkowski sum oftwo multisets A and B is a multiset containing all possible sums of any elementof A and any element of B. This problem was proved to be NP-complete whenmultisets are replaced by sets. This version of the problem is strictly relatedto the factorization of boolean polynomials that turns out to be NP-complete aswell. When multisets are considered, the problem is equivalent to thefactorization of polynomials with non-negative integer coefficients. Thecomputational complexity of both these problems is still unknown. The main contribution of this paper is a heuristic technique for decomposingmultisets of non-negative integers. Experimental results show that ourheuristic decomposes multisets of hundreds of elements within secondsindependently of the magnitude of numbers belonging to the multisets. Ourheuristic can be used also for factoring polynomials in N[x]. We show that,when the degree of the polynomials gets larger, our technique is much fasterthan the state-of-the-art algorithms implemented in commercial software likeMathematica and MatLab.

12. Series acceleration formulas obtained from experimentally discovered hypergeometric recursions

Paul Levrie ; John Campbell.
In 2010, Kh. Hessami Pilehrood and T. Hessami Pilehrood introduced generating function identities used to obtain series accelerations for values of Dirichlet's $\beta$ function, via the Markov--Wilf--Zeilberger method. Inspired by these past results, together with related results introduced by Chu et al., we introduce a variety of hypergeometric recurrences. We prove these recurrences using the WZ method, and we apply these recurrences to obtain series acceleration identities. We introduce a family of summations generalizing a Ramanujan-type series for $\frac{1}{\pi^2}$ due to Guillera, and a family of summations generalizing an accelerated series for Catalan's constant due to Lupa\c{s}, and many related results.