Ke Liu ; Mei Lu.
Let $H=(V,F)$ be a simple hypergraph without loops. $H$ is called linear if
$|f\cap g|\le 1$ for any $f,g\in F$ with $f\not=g$. The $2$-section of $H$,
denoted by $[H]_2$, is a graph with $V([H]_2)=V$ and for any $ u,v\in
V([H]_2)$, $uv\in E([H]_2)$ if and only if there is $ f\in F$ such that $u,v\in
f$. The treewidth of a graph is an important invariant in structural and
algorithmic graph theory. In this paper, we consider the treewidth of the
$2$-section of a linear hypergraph. We will use the minimum degree, maximum
degree, anti-rank and average rank of a linear hypergraph to determine the
upper and lower bounds of the treewidth of its $2$-section. Since for any graph
$G$, there is a linear hypergraph $H$ such that $[H]_2\cong G$, we provide a
method to estimate the bound of treewidth of graph by the parameters of the
hypergraph.
Section:
Graph Theory
Nicolas Grelier ; Saeed Gh. Ilchi ; Tillmann Miltzow ; Shakhar Smorodinsky.
A family S of convex sets in the plane defines a hypergraph H = (S, E) as
follows. Every subfamily S' of S defines a hyperedge of H if and only if there
exists a halfspace h that fully contains S' , and no other set of S is fully
contained in h. In this case, we say that h realizes S'. We say a set S is
shattered, if all its subsets are realized. The VC-dimension of a hypergraph H
is the size of the largest shattered set. We show that the VC-dimension for
pairwise 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 (not
necessarily disjoint) is unbounded. We provide a quadratic lower bound in the
number of pairs of intersecting sets in a shattered family of convex sets in
the plane. We also show that the VC-dimension is unbounded for pairwise
disjoint 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 be
shattered. We give two exemplary applications. One for a geometric set cover
problem and one for a range-query data structure problem, to motivate our
findings.
Section:
Combinatorics
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 common
subgraph of the compared graphs and depends on the structural properties
outside of the common subgraph. There was no known efficient algorithm for the
problem of determining the Hausdorff distance between two trees, and in this
paper we present a polynomial-time algorithm for it. The algorithm is recursive
and it utilizes the divide and conquer technique. As a subtask it also uses the
procedure that is based on the well known graph algorithm of finding the
maximum bipartite matching.
Section:
Discrete Algorithms
Yan Li ; Xin Zhang.
An outer-1-planar graph is a graph admitting a drawing in the plane so that
all vertices appear in the outer region of the drawing and every edge crosses
at most one other edge. This paper establishes the local structure of
outer-1-planar graphs by proving that each outer-1-planar graph contains one of
the seventeen fixed configurations, and the list of those configurations is
minimal in the sense that for each fixed configuration there exist
outer-1-planar graphs containing this configuration that do not contain any of
another sixteen configurations. There are two interesting applications of this
structural theorem. First of all, we conclude that every (resp. maximal)
outer-1-planar graph of minimum degree at least 2 has an edge with the sum of
the degrees of its two end-vertices being at most 9 (resp. 7), and this upper
bound is sharp. On the other hand, we show that the list 3-dynamic chromatic
number of every outer-1-planar graph is at most 6, and this upper bound is best
possible.
Section:
Graph Theory
Zhanar Berikkyzy ; Axel Brandt ; Sogol Jahanbekam ; Victor Larsen ; Danny Rorabaugh.
A graph $G$ is $k$-$weighted-list-antimagic$ if for any vertex weighting
$\omega\colon V(G)\to\mathbb{R}$ and any list assignment $L\colon
E(G)\to2^{\mathbb{R}}$ with $|L(e)|\geq |E(G)|+k$ there exists an edge labeling
$f$ such that $f(e)\in L(e)$ for all $e\in E(G)$, labels of edges are pairwise
distinct, and the sum of the labels on edges incident to a vertex plus the
weight of that vertex is distinct from the sum at every other vertex. In this
paper we prove that every graph on $n$ vertices having no $K_1$ or $K_2$
component is $\lfloor{\frac{4n}{3}}\rfloor$-weighted-list-antimagic.
An oriented graph $G$ is $k$-$oriented-antimagic$ if there exists an
injective edge labeling from $E(G)$ into $\{1,\dotsc,|E(G)|+k\}$ such that the
sum of the labels on edges incident to and oriented toward a vertex minus the
sum of the labels on edges incident to and oriented away from that vertex is
distinct from the difference of sums at every other vertex. We prove that every
graph on $n$ vertices with no $K_1$ component admits an orientation that is
$\lfloor{\frac{2n}{3}}\rfloor$-oriented-antimagic.
Section:
Graph Theory
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 can
actually be found in that sequence as segments (up to exchange of letters in
the infinite case). This result was previously attributed to unpublished work
by D. Guaiana and may also be derived from publications of A. Shur only
available in Russian. We also identify the (finitely many) finite binary
patterns that appear non trivially, in the sense that they are obtained by
applying an endomorphism that does not map the set of all segments of the
sequence into itself.
Section:
Automata, Logic and Semantics
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 hypercube
bins. Epstein and van Stee [SIAM J. Comput. 35 (2005)] showed that the
asymptotic performance ratio $\rho$ of the online bounded space variant is
$\Omega(\log d)$ and $O(d/\log d)$, and conjectured that it is $\Theta(\log
d)$. We show that $\rho$ is in fact $\Theta(d/\log d)$, using probabilistic
arguments.
Section:
Discrete Algorithms
Laurent Feuilloley.
A distributed graph algorithm is basically an algorithm where every node of a
graph can look at its neighborhood at some distance in the graph and chose its
output. As distributed environment are subject to faults, an important issue is
to be able to check that the output is correct, or in general that the network
is in proper configuration with respect to some predicate. One would like this
checking to be very local, to avoid using too much resources. Unfortunately
most predicates cannot be checked this way, and that is where certification
comes into play. Local certification (also known as proof-labeling schemes,
locally checkable proofs or distributed verification) consists in assigning
labels to the nodes, that certify that the configuration is correct. There are
several point of view on this topic: it can be seen as a part of
self-stabilizing algorithms, as labeling problem, or as a non-deterministic
distributed decision.
This paper is an introduction to the domain of local certification, giving an
overview of the history, the techniques and the current research directions.
Section:
Distributed Computing and Networking
Stijn Cambie.
In this paper, we prove a collection of results on graphical indices. We
determine the extremal graphs attaining the maximal generalized Wiener index
(e.g. the hyper-Wiener index) among all graphs with given matching number or
independence number. This generalizes some work of Dankelmann, as well as some
work of Chung. We also show alternative proofs for two recents results on
maximizing the Wiener index and external Wiener index by deriving it from
earlier results. We end with proving two conjectures. We prove that the maximum
for the difference of the Wiener index and the eccentricity is attained by the
path if the order $n$ is at least $9$ and that the maximum weighted Szeged
index of graphs of given order is attained by the balanced complete bipartite
graphs.
Section:
Graph Theory
Guillaume Ducoffe ; Michel Habib ; Laurent Viennot.
When can we compute the diameter of a graph in quasi linear time? We address
this question for the class of {\em split graphs}, that we observe to be the
hardest instances for deciding whether the diameter is at most two. We stress
that although the diameter of a non-complete split graph can only be either $2$
or $3$, under the Strong Exponential-Time Hypothesis (SETH) we cannot compute
the diameter of an $n$-vertex $m$-edge split graph in less than quadratic time
-- in the size $n+m$ of the input. Therefore it is worth to study the
complexity of diameter computation on {\em subclasses} of split graphs, in
order to better understand the complexity border. Specifically, we consider the
split graphs with bounded {\em clique-interval number} and their complements,
with the former being a natural variation of the concept of interval number for
split graphs that we introduce in this paper. We first discuss the relations
between the clique-interval number and other graph invariants such as the
classic interval number of graphs, the treewidth, the {\em VC-dimension} and
the {\em stabbing number} of a related hypergraph. Then, in part based on these
above relations, we almost completely settle the complexity of diameter
computation on these subclasses of split graphs: - For the $k$-clique-interval
split graphs, we can compute their diameter in truly subquadratic time if
$k={\cal O}(1)$, and even in quasi linear time if $k=o(\log{n})$ and in
addition a corresponding ordering of the […]
Section:
Graph Theory
Yuan Li ; Frank Ingram ; Huaming Zhang.
Boolean nested canalizing functions (NCFs) have important applications in
molecular 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 develop
a direct proof of the certificate complexity formula of an NCF. Symmetry is
another interesting property of Boolean functions and we significantly simplify
the proofs of some recent theorems about partial symmetry of NCFs. We also
describe the algebraic normal form of $s$-symmetric NCFs. We obtain the general
formula of the cardinality of the set of $n$-variable $s$-symmetric Boolean
NCFs for $s=1,\dots,n$. In particular, we enumerate the strongly asymmetric
Boolean NCFs.
Section:
Combinatorics
Gunnar Brinkmann ; Thomas Tucker ; Nico Van Cleemput.
In this article we present theoretical and computational results on the
existence of polyhedral embeddings of graphs. The emphasis is on cubic graphs.
We also describe an efficient algorithm to compute all polyhedral embeddings of
a given cubic graph and constructions for cubic graphs with some special
properties of their polyhedral embeddings. Some key results are that even cubic
graphs with a polyhedral embedding on the torus can also have polyhedral
embeddings in arbitrarily high genus, in fact in a genus {\em close} to the
theoretical maximum for that number of vertices, and that there is no bound on
the number of genera in which a cubic graph can have a polyhedral embedding.
While these results suggest a large variety of polyhedral embeddings,
computations for up to 28 vertices suggest that by far most of the cubic graphs
do not have a polyhedral embedding in any genus and that the ratio of these
graphs is increasing with the number of vertices.
Section:
Graph Theory
Swapnil Garg.
Fici, Restivo, Silva, and Zamboni define a $k$-antipower to be a word
composed of $k$ pairwise distinct, concatenated words of equal length. Berger
and Defant conjecture that for any sufficiently well-behaved aperiodic morphic
word $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 extend
their result to alphabets of arbitrary finite size and characterize those words
for which the result does not hold. We also prove their conjecture in the
specific case of the Fibonacci word.
Section:
Combinatorics
Dániel Gerbner ; Máté Vizer.
We are given $n$ balls and an unknown coloring of them with two colors. Our
goal is to find a ball that belongs to the larger color class, or show that the
color classes have the same size. We can ask sets of $k$ balls as queries, and
the problem has different variants, according to what the answers to the
queries can be. These questions has attracted several researchers, but the
focus of most research was the adaptive version, where queries are decided
sequentially, after learning the answer to the previous query. Here we study
the non-adaptive version, where all the queries have to be asked at the same
time.
Section:
Analysis of Algorithms
Hadi Alizadeh ; Didem Gözüpek.
A paired dominating set $P$ is a dominating set with the additional property
that $P$ has a perfect matching. While the maximum cardainality of a minimal
dominating set in a graph $G$ is called the upper domination number of $G$,
denoted by $\Gamma(G)$, the maximum cardinality of a minimal paired dominating
set in $G$ is called the upper paired domination number of $G$, denoted by
$\Gamma_{pr}(G)$. By Henning and Pradhan (2019), we know that
$\Gamma_{pr}(G)\leq 2\Gamma(G)$ for any graph $G$ without isolated vertices. We
focus on the graphs satisfying the equality $\Gamma_{pr}(G)= 2\Gamma(G)$. We
give characterizations for two special graph classes: bipartite and unicyclic
graphs with $\Gamma_{pr}(G)= 2\Gamma(G)$ by using the results of Ulatowski
(2015). Besides, we study the graphs with $\Gamma_{pr}(G)= 2\Gamma(G)$ and a
restricted girth. In this context, we provide two characterizations: one for
graphs with $\Gamma_{pr}(G)= 2\Gamma(G)$ and girth at least 6 and the other for
$C_3$-free cactus graphs with $\Gamma_{pr}(G)= 2\Gamma(G)$. We also pose the
characterization of the general case of $C_3$-free graphs with $\Gamma_{pr}(G)=
2\Gamma(G)$ as an open question.
Section:
Graph Theory