Michał Tuczyński ; Przemysław Wenus ; Krzysztof Węsek.
Let $f:V\rightarrow\mathbb{Z}_k$ be a vertex labeling of a hypergraph
$H=(V,E)$. This labeling induces an~edge labeling of $H$ defined by
$f(e)=\sum_{v\in e}f(v)$, where the sum is taken modulo $k$. We say that $f$ is
$k$-cordial if for all $a, b \in \mathbb{Z}_k$ the number of vertices with
label $a$ differs by at most $1$ from the number of vertices with label $b$ and
the analogous condition holds also for labels of edges. If $H$ admits a
$k$-cordial labeling then $H$ is called $k$-cordial. The existence of
$k$-cordial labelings has been investigated for graphs for decades.
Hovey~(1991) conjectured that every tree $T$ is $k$-cordial for every $k\ge 2$.
Cichacz, Görlich and Tuza~(2013) were first to investigate the analogous
problem for hypertrees, that is, connected hypergraphs without cycles. The main
results of their work are that every $k$-uniform hypertree is $k$-cordial for
every $k\ge 2$ and that every hypertree with $n$ or $m$ odd is $2$-cordial.
Moreover, they conjectured that in fact all hypertrees are $2$-cordial. In this
article, we confirm the conjecture of Cichacz et al. and make a step further by
proving that for $k\in\{2,3\}$ every hypertree is $k$-cordial.
Section:
Graph Theory
Huazhong Lü ; Tingzeng Wu.
Edge-connectivity is a classic measure for reliability of a network in the
presence of edge failures. $k$-restricted edge-connectivity is one of the
refined indicators for fault tolerance of large networks. Matching preclusion
and conditional matching preclusion are two important measures for the
robustness of networks in edge fault scenario. In this paper, we show that the
DCell network $D_{k,n}$ is super-$\lambda$ for $k\geq2$ and $n\geq2$,
super-$\lambda_2$ for $k\geq3$ and $n\geq2$, or $k=2$ and $n=2$, and
super-$\lambda_3$ for $k\geq4$ and $n\geq3$. Moreover, as an application of
$k$-restricted edge-connectivity, we study the matching preclusion number and
conditional matching preclusion number, and characterize the corresponding
optimal solutions of $D_{k,n}$. In particular, we have shown that $D_{1,n}$ is
isomorphic to the $(n,k)$-star graph $S_{n+1,2}$ for $n\geq2$.
Section:
Graph Theory
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 […]
Section:
Graph Theory
Diane Castonguay ; Erika M. M. Coelho ; Hebert Coelho ; Julliano R. Nascimento.
In the geodetic convexity, a set of vertices $S$ of a graph $G$ is
$\textit{convex}$ if all vertices belonging to any shortest path between two
vertices of $S$ lie in $S$. The cardinality $con(G)$ of a maximum proper convex
set $S$ of $G$ is the $\textit{convexity number}$ of $G$. The
$\textit{complementary prism}$ $G\overline{G}$ of a graph $G$ arises from the
disjoint union of the graph $G$ and $\overline{G}$ by adding the edges of a
perfect matching between the corresponding vertices of $G$ and $\overline{G}$.
In this work, we we prove that the decision problem related to the convexity
number is NP-complete even restricted to complementary prisms, we determine
$con(G\overline{G})$ when $G$ is disconnected or $G$ is a cograph, and we
present a lower bound when $diam(G) \neq 3$.
Section:
Graph Theory
Jan Goedgebeur ; Carol T. Zamfirescu.
A graph $G$ is almost hypohamiltonian (a.h.) if $G$ is non-hamiltonian, there
exists a vertex $w$ in $G$ such that $G - w$ is non-hamiltonian, and $G - v$ is
hamiltonian for every vertex $v \ne w$ in $G$. The second author asked in [J.
Graph Theory 79 (2015) 63--81] for all orders for which a.h. graphs exist. Here
we solve this problem. To this end, we present a specialised algorithm which
generates complete sets of a.h. graphs for various orders. Furthermore, we show
that the smallest cubic a.h. graphs have order 26. We provide a lower bound for
the order of the smallest planar a.h. graph and improve the upper bound for the
order of the smallest planar a.h. graph containing a cubic vertex. We also
determine the smallest planar a.h. graphs of girth 5, both in the general and
cubic case. Finally, we extend a result of Steffen on snarks and improve two
bounds on longest paths and longest cycles in polyhedral graphs due to
Jooyandeh, McKay, {\"O}sterg{\aa}rd, Pettersson, and the second author.
Section:
Graph Theory
Tianlong Ma ; Yaping Mao ; Eddie Cheng ; Christopher Melekian.
The \emph{matching preclusion number} of a graph is the minimum number of
edges whose deletion results in a graph that has neither perfect matchings nor
almost perfect matchings. As a generalization, Liu and Liu recently introduced
the concept of fractional matching preclusion number. The \emph{fractional
matching preclusion number} of $G$ is the minimum number of edges whose
deletion leaves the resulting graph without a fractional perfect matching. The
\emph{fractional strong matching preclusion number} of $G$ is the minimum
number of vertices and edges whose deletion leaves the resulting graph without
a fractional perfect matching. In this paper, we obtain the fractional matching
preclusion number and the fractional strong matching preclusion number for
generalized augmented cubes. In addition, all the optimal fractional strong
matching preclusion sets of these graphs are categorized.
Section:
Distributed Computing and Networking
Andrzej Dudek ; Andrzej Ruciński.
For integers $k\ge 2$ and $\ell\ge 0$, a $k$-uniform hypergraph is called a
loose path of length $\ell$, and denoted by $P_\ell^{(k)}$, if it consists of
$\ell $ edges $e_1,\dots,e_\ell$ such that $|e_i\cap e_j|=1$ if $|i-j|=1$ and
$e_i\cap e_j=\emptyset$ if $|i-j|\ge2$. In other words, each pair of
consecutive edges intersects on a single vertex, while all other pairs are
disjoint. Let $R(P_\ell^{(k)};r)$ be the minimum integer $n$ such that every
$r$-edge-coloring of the complete $k$-uniform hypergraph $K_n^{(k)}$ yields a
monochromatic copy of $P_\ell^{(k)}$. In this paper we are mostly interested in
constructive upper bounds on $R(P_\ell^{(k)};r)$, meaning that on the cost of
possibly enlarging the order of the complete hypergraph, we would like to
efficiently find a monochromatic copy of $P_\ell^{(k)}$ in every coloring. In
particular, we show that there is a constant $c>0$ such that for all $k\ge 2$,
$\ell\ge3$, $2\le r\le k-1$, and $n\ge k(\ell+1)r(1+\ln(r))$, there is an
algorithm such that for every $r$-edge-coloring of the edges of $K_n^{(k)}$, it
finds a monochromatic copy of $P_\ell^{(k)}$ in time at most $cn^k$. We also
prove a non-constructive upper bound $R(P_\ell^{(k)};r)\le(k-1)\ell r$.
Section:
Graph Theory
Kevin Durant ; Stephan Wagner.
A centroid node in a tree is a node for which the sum of the distances to all
other nodes attains its minimum, or equivalently a node with the property that
none of its branches contains more than half of the other nodes. We generalise
some known results regarding the behaviour of centroid nodes in random
recursive trees (due to Moon) to the class of very simple increasing trees,
which also includes the families of plane-oriented and $d$-ary increasing
trees. In particular, we derive limits of distributions and moments for the
depth and label of the centroid node nearest to the root, as well as for the
size of the subtree rooted at this node.
Section:
Combinatorics
Arash Ahadi ; Ali Dehghan.
The satisfiability problem is known to be $\mathbf{NP}$-complete in general
and for many restricted cases. One way to restrict instances of $k$-SAT is to
limit the number of times a variable can be occurred. It was shown that for an
instance of 4-SAT with the property that every variable appears in exactly 4
clauses (2 times negated and 2 times not negated), determining whether there is
an assignment for variables such that every clause contains exactly two true
variables and two false variables is $\mathbf{NP}$-complete. In this work, we
show that deciding the satisfiability of 3-SAT with the property that every
variable appears in exactly four clauses (two times negated and two times not
negated), and each clause contains at least two distinct variables is $
\mathbf{NP} $-complete. We call this problem $(2/2/3)$-SAT. For an $r$-regular
graph $G = (V,E)$ with $r\geq 3$, it was asked in [Discrete Appl. Math.,
160(15):2142--2146, 2012] to determine whether for a given independent set $T $
there is an independent dominating set $D$ that dominates $T$ such that $ T
\cap D =\varnothing $? As an application of $(2/2/3)$-SAT problem we show that
for every $r\geq 3$, this problem is $ \mathbf{NP} $-complete. Among other
results, we study the relationship between 1-perfect codes and the incidence
coloring of graphs and as another application of our complexity results, we
prove that for a given cubic graph $G$ deciding whether $G$ is 4-incidence
colorable is $ \mathbf{NP} $-complete.
Section:
Graph Theory
Ferhat Alkan ; Türker Bıyıkoğlu ; Marc Demange ; Cesim Erten.
We consider the constrained graph alignment problem which has applications in
biological network analysis. Given two input graphs $G_1=(V_1,E_1),
G_2=(V_2,E_2)$, a pair of vertex mappings induces an {\it edge conservation} if
the vertex pairs are adjacent in their respective graphs. %In general terms The
goal is to provide a one-to-one mapping between the vertices of the input
graphs in order to maximize edge conservation. However the allowed mappings are
restricted since each vertex from $V_1$ (resp. $V_2$) is allowed to be mapped
to at most $m_1$ (resp. $m_2$) specified vertices in $V_2$ (resp. $V_1$). Most
of results in this paper deal with the case $m_2=1$ which attracted most
attention in the related literature. We formulate the problem as a maximum
independent set problem in a related {\em conflict graph} and investigate
structural properties of this graph in terms of forbidden subgraphs. We are
interested, in particular, in excluding certain wheals, fans, cliques or claws
(all terms are defined in the paper), which corresponds in excluding certain
cycles, paths, cliques or independent sets in the neighborhood of each vertex.
Then, we investigate algorithmic consequences of some of these properties,
which illustrates the potential of this approach and raises new horizons for
further works. In particular this approach allows us to reinterpret a known
polynomial case in terms of conflict graph and to improve known approximation
and fixed-parameter tractability results […]
Section:
Discrete Algorithms
Kitty Meeks ; Dominik K. Vu.
The problem of determining the number of "flooding operations" required to
make a given coloured graph monochromatic in the one-player combinatorial game
Flood-It has been studied extensively from an algorithmic point of view, but
basic questions about the maximum number of moves that might be required in the
worst case remain unanswered. We begin a systematic investigation of such
questions, with the goal of determining, for a given graph, the maximum number
of moves that may be required, taken over all possible colourings. We give
several upper and lower bounds on this quantity for arbitrary graphs and show
that all of the bounds are tight for trees; we also investigate how much the
upper bounds can be improved if we restrict our attention to graphs with higher
edge-density.
Section:
Graph Theory
Masaki Nakanishi ; Abuzer Yakaryılmaz ; Aida Gainutdinova.
We show that one-way quantum one-counter automaton with zero-error is more
powerful than its probabilistic counterpart on promise problems. Then, we
obtain a similar separation result between Las Vegas one-way probabilistic
one-counter automaton and one-way deterministic one-counter automaton.
We also obtain new results on classical counter automata regarding language
recognition. It was conjectured that one-way probabilistic one blind-counter
automata cannot recognize Kleene closure of equality language [A. Yakaryilmaz:
Superiority of one-way and realtime quantum machines. RAIRO - Theor. Inf. and
Applic. 46(4): 615-641 (2012)]. We show that this conjecture is false, and also
show several separation results for blind/non-blind counter automata.
Section:
Automata, Logic and Semantics
Audace A. V. Dossou-Olory ; Stephan Wagner.
The quantity that captures the asymptotic value of the maximum number of
appearances of a given topological tree (a rooted tree with no vertices of
outdegree $1$) $S$ with $k$ leaves in an arbitrary tree with sufficiently large
number of leaves is called the inducibility of $S$. Its precise value is known
only for some specific families of trees, most of them exhibiting a symmetrical
configuration. In an attempt to answer a recent question posed by Czabarka,
Székely, and the second author of this article, we provide bounds for the
inducibility $J(A_5)$ of the $5$-leaf binary tree $A_5$ whose branches are a
single leaf and the complete binary tree of height $2$. It was indicated before
that $J(A_5)$ appears to be `close' to $1/4$. We can make this precise by
showing that $0.24707\ldots \leq J(A_5) \leq 0.24745\ldots$. Furthermore, we
also consider the problem of determining the inducibility of the tree $Q_4$,
which is the only tree among $4$-leaf topological trees for which the
inducibility is unknown.
Section:
Combinatorics
Kengo Enami.
Whitney's theorem states that every 3-connected planar graph is uniquely
embeddable on the sphere. On the other hand, it has many inequivalent
embeddings on another surface. We shall characterize structures of a
$3$-connected $3$-regular planar graph $G$ embedded on the projective-plane,
the torus and the Klein bottle, and give a one-to-one correspondence between
inequivalent embeddings of $G$ on each surface and some subgraphs of the dual
of $G$ embedded on the sphere. These results enable us to give explicit bounds
for the number of inequivalent embeddings of $G$ on each surface, and propose
effective algorithms for enumerating and counting these embeddings.
Section:
Graph Theory
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.
Section:
Graph Theory
Colin Defant.
After fixing a canonical ordering (or labeling) of the elements of a finite
poset, one can associate each linear extension of the poset with a permutation.
Some recent papers consider specific families of posets and ask how many linear
extensions give rise to permutations that avoid certain patterns. We build off
of two of these papers. We first consider pattern avoidance in $k$-ary heaps,
where we obtain a general result that proves a conjecture of Levin, Pudwell,
Riehl, and Sandberg in a special case. We then prove some conjectures that
Anderson, Egge, Riehl, Ryan, Steinke, and Vaughan made about pattern-avoiding
linear extensions of rectangular posets.
Section:
Combinatorics
Zongwen Bai ; Jianhua Tu ; Yongtang Shi.
Given a graph $G=(V,E)$ and a positive integer $t\geq2$, the task in the
vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices
$F\subseteq V$ such that every path of order $t$ in $G$ contains at least one
vertex from $F$. The $VCP_t$ problem is NP-complete for any integer $t\geq2$
and has many applications in real world. Recently, the authors presented a
dynamic programming algorithm running in time $4^p\cdot n^{O(1)}$ for the
$VCP_3$ problem on $n$-vertex graphs with treewidth $p$. In this paper, we
propose an improvement of it and improved the time-complexity to $3^p\cdot
n^{O(1)}$.
The connected vertex cover $P_3$ ($CVCP_3$) problem is the connected
variation of the $VCP_3$ problem where $G[F]$ is required to be connected.
Using the Cut\&Count technique, we give a randomized algorithm with runtime
$4^p\cdot n^{O(1)}$ for the $CVCP_3$ problem on $n$-vertex graphs with
treewidth $p$.
Section:
Discrete Algorithms
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 .
Section:
Graph Theory
Daniel J. Rosenkrantz ; Madhav V. Marathe ; S. S. Ravi ; Richard E. Stearns.
Many researchers have studied symmetry properties of various Boolean
functions. A class of Boolean functions, called nested canalyzing functions
(NCFs), has been used to model certain biological phenomena. We identify some
interesting relationships between NCFs, symmetric Boolean functions and a
generalization of symmetric Boolean functions, which we call $r$-symmetric
functions (where $r$ is the symmetry level). Using a normalized representation
for NCFs, we develop a characterization of when two variables of an NCF are
symmetric. Using this characterization, we show that the symmetry level of an
NCF $f$ can be easily computed given a standard representation of $f$. We also
present an algorithm for testing whether a given $r$-symmetric function is an
NCF. Further, we show that for any NCF $f$ with $n$ variables, the notion of
strong asymmetry considered in the literature is equivalent to the property
that $f$ is $n$-symmetric. We use this result to derive a closed form
expression for the number of $n$-variable Boolean functions that are NCFs and
strongly asymmetric. We also identify all the Boolean functions that are NCFs
and symmetric.
Section:
Discrete Algorithms