vol. 21 no. 4


1. On cordial labeling of hypertrees

Tuczyński, Michał ; Wenus, Przemysław ; Węsek, Krzysztof.
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 […]
Section: Graph Theory

2. Super edge-connectivity and matching preclusion of data center networks

Lü, Huazhong ; Wu, Tingzeng.
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

3. A note on the convexity number for complementary prisms

Castonguay, Diane ; Coelho, Erika M. M. ; Coelho, Hebert ; Nascimento, Julliano R..
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

4. On almost hypohamiltonian graphs

Goedgebeur, Jan ; Zamfirescu, Carol T..
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 […]
Section: Graph Theory

5. Fractional matching preclusion for generalized augmented cubes

Ma, Tianlong ; Mao, Yaping ; Cheng, Eddie ; Melekian, Christopher.
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

6. $(2/2/3)$-SAT problem and its applications in dominating set problems

Ahadi, Arash ; Dehghan, Ali.
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 […]
Section: Graph Theory

7. Extremal properties of flood-filling games

Meeks, Kitty ; Vu, Dominik K..
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