vol. 23, no. 3


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

2. On the VC-dimension of half-spaces with respect to convex sets

Nicolas Grelier ; Saeed Gh. Ilchi ; Tillmann Miltzow ; Shakhar Smorodinsky.
A family S of convex sets in the plane defines a hypergraph H = (S, E) asfollows. Every subfamily S' of S defines a hyperedge of H if and only if thereexists a halfspace h that fully contains S' , and no other set of S is fullycontained in h. In this case, we say that h realizes S'. We say a set S isshattered, if all its subsets are realized. The VC-dimension of a hypergraph His the size of the largest shattered set. We show that the VC-dimension forpairwise disjoint convex sets in the plane is bounded by 3, and this is tight.In contrast, we show the VC-dimension of convex sets in the plane (notnecessarily disjoint) is unbounded. We provide a quadratic lower bound in thenumber of pairs of intersecting sets in a shattered family of convex sets inthe plane. We also show that the VC-dimension is unbounded for pairwisedisjoint convex sets in R^d , for d > 2. We focus on, possibly intersecting,segments in the plane and determine that the VC-dimension is always at most 5.And this is tight, as we construct a set of five segments that can beshattered. We give two exemplary applications. One for a geometric set coverproblem and one for a range-query data structure problem, to motivate ourfindings.

3. Determining the Hausdorff Distance Between Trees in Polynomial Time

Aleksander Kelenc.
The Hausdorff distance is a relatively new measure of similarity of graphs.The notion of the Hausdorff distance considers a special kind of a commonsubgraph of the compared graphs and depends on the structural propertiesoutside of the common subgraph. There was no known efficient algorithm for theproblem of determining the Hausdorff distance between two trees, and in thispaper we present a polynomial-time algorithm for it. The algorithm is recursiveand it utilizes the divide and conquer technique. As a subtask it also uses theprocedure that is based on the well known graph algorithm of finding themaximum bipartite matching.

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

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

6. Binary patterns in the Prouhet-Thue-Morse sequence

Jorge Almeida ; Ondřej Klíma.
We show that, with the exception of the words $a^2ba^2$ and $b^2ab^2$, all(finite or infinite) binary patterns in the Prouhet-Thue-Morse sequence canactually be found in that sequence as segments (up to exchange of letters inthe infinite case). This result was previously attributed to unpublished workby D. Guaiana and may also be derived from publications of A. Shur onlyavailable in Russian. We also identify the (finitely many) finite binarypatterns that appear non trivially, in the sense that they are obtained byapplying an endomorphism that does not map the set of all segments of thesequence into itself.

7. A tight lower bound for the online bounded space hypercube bin packing problem

Yoshiharu Kohayakawa ; Flávio Keidi Miyazawa ; Yoshiko Wakabayashi.
In the $d$-dimensional hypercube bin packing problem, a given list of$d$-dimensional hypercubes must be packed into the smallest number of hypercubebins. Epstein and van Stee [SIAM J. Comput. 35 (2005)] showed that theasymptotic performance ratio $\rho$ of the online bounded space variant is$\Omega(\log d)$ and $O(d/\log d)$, and conjectured that it is $\Theta(\logd)$. We show that $\rho$ is in fact $\Theta(d/\log d)$, using probabilisticarguments.

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

9. Introduction to local certification

Laurent Feuilloley.
A distributed graph algorithm is basically an algorithm where every node of agraph can look at its neighborhood at some distance in the graph and chose itsoutput. As distributed environment are subject to faults, an important issue isto be able to check that the output is correct, or in general that the networkis in proper configuration with respect to some predicate. One would like thischecking to be very local, to avoid using too much resources. Unfortunatelymost predicates cannot be checked this way, and that is where certificationcomes into play. Local certification (also known as proof-labeling schemes,locally checkable proofs or distributed verification) consists in assigninglabels to the nodes, that certify that the configuration is correct. There areseveral point of view on this topic: it can be seen as a part ofself-stabilizing algorithms, as labeling problem, or as a non-deterministicdistributed decision. This paper is an introduction to the domain of local certification, giving anoverview of the history, the techniques and the current research directions.

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

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

12. Certificate complexity and symmetry of nested canalizing functions

Yuan Li ; Frank Ingram ; Huaming Zhang.
Boolean nested canalizing functions (NCFs) have important applications inmolecular regulatory networks, engineering and computer science. In this paper,we study their certificate complexity. For both Boolean values $b\in\{0,1\}$,we obtain a formula for $b$-certificate complexity and consequently, we developa direct proof of the certificate complexity formula of an NCF. Symmetry isanother interesting property of Boolean functions and we significantly simplifythe proofs of some recent theorems about partial symmetry of NCFs. We alsodescribe the algebraic normal form of $s$-symmetric NCFs. We obtain the generalformula of the cardinality of the set of $n$-variable $s$-symmetric BooleanNCFs for $s=1,\dots,n$. In particular, we enumerate the strongly asymmetricBoolean NCFs.

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

14. Antipowers in Uniform Morphic Words and the Fibonacci Word

Swapnil Garg.
Fici, Restivo, Silva, and Zamboni define a $k$-antipower to be a wordcomposed of $k$ pairwise distinct, concatenated words of equal length. Bergerand Defant conjecture that for any sufficiently well-behaved aperiodic morphicword $w$, there exists a constant $c$ such that for any $k$ and any index $i$,a $k$-antipower with block length at most $ck$ starts at the $i$th position of$w$. They prove their conjecture in the case of binary words, and we extendtheir result to alphabets of arbitrary finite size and characterize those wordsfor which the result does not hold. We also prove their conjecture in thespecific case of the Fibonacci word.

15. On non-adaptive majority problems of large query size

Dániel Gerbner ; Máté Vizer.
We are given $n$ balls and an unknown coloring of them with two colors. Ourgoal is to find a ball that belongs to the larger color class, or show that thecolor classes have the same size. We can ask sets of $k$ balls as queries, andthe problem has different variants, according to what the answers to thequeries can be. These questions has attracted several researchers, but thefocus of most research was the adaptive version, where queries are decidedsequentially, after learning the answer to the previous query. Here we studythe non-adaptive version, where all the queries have to be asked at the sametime.

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

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