The list L(2,1)-labeling of planar graphs

Let $\mathbf{N}$ be the set of all positive integers. A list assignment of a graph $G$ is a function $L:V\left(G\right)?2^{\mathbf{N}}$ that assigns each vertex $v$ a list $L\left(v\right)$ for all $v\in V\left(G\right)$. We say that $G$ is $L$-$(2,1)$-choosable if there exists a function $?$ such that $?\left(v\right)\in L\left(v\right)$ for all $v\in V\left(G\right)$, $|?\left(u\right)??\left(v\right)|\ge 2$ if $u$ and $v$ are adjacent, and $|?\left(u\right)??\left(v\right)|\ge 1$ if $u$ and $v$ are at distance 2. The list-$L(2,1)$-labeling number ${\lambda }_l\left(G\right)$ of $G$ is the minimum $k$ such that for every list assignment $L=\{L\left(v\right):|L\left(v\right)|=k,v\in V\left(G\right)\}$, $G$ is $L$-$(2,1)$-choosable. We prove that if $G$ is a planar graph with girth $g\ge 8$ and its maximum degree $\Delta$ is large enough, then ${\lambda }_l\left(G\right)\le \Delta +3$. There are graphs with large enough $\Delta$ and $g\ge 8$ having ${\lambda }_l\left(G\right)=\Delta +3$.     

Existence of incomplete canonical Kirkman packing designs

For $u,v$ positive integers with $u\equiv v\equiv 4\left(mod6\right)$, let ICKPD$(u,v)$ denote a canonical Kirkman packing of order $u$ missing one of order $v$. In this paper, it is shown that the necessary condition for existence of an ICKPD$(u,v)$, namely $u\ge 3v+4$, is sufficient with a definite exception $(u,v)=(16,4)$, and except possibly when $v>76$, $v\equiv 4\left(mod12\right)$ and $u\in \{3v+4,3v+10\}$.     

A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs

Let $G$ be a balanced bipartite graph of order $2n\ge 4$, and let ${\sigma }_{1,1}\left(G\right)$ be the minimum degree sum of two non-adjacent vertices in different partite sets of $G$. In 1963, Moon and Moser proved that if ${\sigma }_{1,1}\left(G\right)\ge n+1$, then $G$ is hamiltonian. In this note, we show that if $k$ is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly $k$ cycles for sufficiently large graphs. In order to prove this, we also give a ${\sigma }_{1,1}$ condition for the existence of $k$ vertex-disjoint alternating cycles with respect to a chosen perfect matching in $G$.     

On the roots of Wiener polynomials of graphs

The Wiener polynomial of a connected graph $G$ is defined as $W(G;x)=\sum x^{d(u,v)}$, where $d(u,v)$ denotes the distance between $u$ and $v$, and the sum is taken over all unordered pairs of distinct vertices of $G$. We examine the nature and location of the roots of Wiener polynomials of graphs, and in particular trees. We show that while the maximum modulus among all roots of Wiener polynomials of graphs of order $n$ is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)?1$, the maximum modulus among all roots of Wiener polynomials of trees of order $n$ grows linearly in $n$. We prove that the closure of the collection of real roots of Wiener polynomials of all graphs is precisely $(?\infty ,0]$, while in the case of trees, it contains $(?\infty ,?1]$. Finally, we demonstrate that the imaginary parts and (positive) real parts of roots of Wiener polynomials can be arbitrarily large.     

Quasigroups satisfying Stein’s third law with a specified number of idempotents

Quasigroups satisfying Stein’s third law (QSTL for short) have been associated with other types of combinatorial configurations, such as cyclic orthogonal arrays. These have been studied quite extensively over the years by various researchers, including Curt Lindner. An idempotent model of a QSTL of order $v$ (briefly QSTL$\left(v\right)$), corresponds to a perfect Mendelsohn design of order $v$ with block size four (briefly a $(v,4,1)$-PMD) and these are known to exist if and only if $v\equiv 0,1\left(\mathrm{mod}4\right)$, except for $v=4,8$. There is a QSTL$\left(4\right)$ with two idempotents and it is known that a QSTL$\left(8\right)$ contains either $0$ or $4$ idempotents. In this paper, we formally investigate the existence of a QSTL$\left(v\right)$ with a specified number $n$ of idempotent elements, briefly denoted by QSTL$(v,n)$. The necessary conditions for the existence of a QSTL$(v,n)$ are $v\equiv 0,1\left(\mathrm{mod}4\right)$, $0\le n\le v$, and $v?n$ is even. We show that these conditions are also sufficient with few definite exceptions and a handful of possible exceptions. Holey perfect Mendelsohn designs of type $4^n{u}^1$ with block size four (HPMD$\left(4^n{u}^1\right)$ for short) are useful to establish the spectrum of QSTL$(v,n)$. In particular, we show that for $0\le u\le 8$, an HPMD$\left(4^n{u}^1\right)$ exists if and only if $n\ge max(4,?u/2?+1)$, except possibly $(n,u)=(12,1)$.     

Distant total irregularity strength of graphs via random vertex ordering

Let $c:V\cup E\to \{1,2,\dots ,k\}$ be a (not necessarily proper) total colouring of a graph $G=(V,E)$ with maximum degree $\Delta$. Two vertices $u,v\in V$ are sum distinguished if they differ with respect to sums of their incident colours, i.e. $c\left(u\right)+{\sum }_{e?u}c\left(e\right)\ne c\left(v\right)+{\sum }_{e?v}c\left(e\right)$. The least integer $k$ admitting such colouring $c$ under which every $u,v\in V$ at distance $1\le d(u,v)\le r$ in $G$ are sum distinguished is denoted by ${\mathrm{ts}}_r\left(G\right)$. Such graph invariants link the concept of the total vertex irregularity strength of graphs with so-called 1-2-Conjecture, whose concern is the case of $r=1$. Within this paper we combine probabilistic approach with purely combinatorial one in order to prove that ${\mathrm{ts}}_r\left(G\right)\le (2+o\left(1\right)){\Delta }^{r?1}$ for every integer $r\ge 2$ and each graph $G$, thus improving the previously best result: ${\mathrm{ts}}_r\left(G\right)\le 3{\Delta }^{r?1}$.     

On vertex-disjoint cycles and degree sum conditions

This paper considers a degree sum condition sufficient to imply the existence of $k$ vertex-disjoint cycles in a graph $G$. For an integer $t\ge 1$, let ${\sigma }_t\left(G\right)$ be the smallest sum of degrees of $t$ independent vertices of $G$. We prove that if $G$ has order at least $7k+1$ and ${\sigma }_4\left(G\right)\ge 8k?3$, with $k\ge 2$, then $G$ contains $k$ vertex-disjoint cycles. We also show that the degree sum condition on ${\sigma }_4\left(G\right)$ is sharp and conjecture a degree sum condition on ${\sigma }_t\left(G\right)$ sufficient to imply $G$ contains $k$ vertex-disjoint cycles for $k\ge 2$.     

Overlarge sets of resolvable idempotent quasigroups

An idempotent quasigroup $(X,°)$ of order $v$ is called resolvable (denoted by RIQ$\left(v\right)$) if the set of $v(v?1)$ non-idempotent 3-vectors $\{(a,b,a°b):a,b\in X,a\ne b\}$ can be partitioned into $v?1$ disjoint transversals. An overlarge set of idempotent quasigroups of order $v$, briefly by OLIQ$\left(v\right)$, is a collection of $v+1$ IQ$\left(v\right)$s, with all the non-idempotent 3-vectors partitioning all those on a $(v+1)$-set. An OLRIQ$\left(v\right)$ is an OLIQ$\left(v\right)$ with each member IQ$\left(v\right)$ being resolvable. In this paper, it is established that there exists an OLRIQ$\left(v\right)$ for any positive integer $v\ge 3$, except for $v=6$, and except possibly for $v\in \{10,11,14,18,19,23,26,30,51\}$. An OLIQ${}^{?}\left(v\right)$ is another type of restricted OLIQ$\left(v\right)$ in which each member IQ$\left(v\right)$ has an idempotent orthogonal mate. It is shown that an OLIQ${}^{?}\left(v\right)$ exists for any positive integer $v\ge 4$, except for $v=6$, and except possibly for $v\in \{14,15,19,23,26,27,30\}$.     

On mutually independent hamiltonian paths

Let $P_1=〈v_1,v_2,v_3,\dots ,v_n〉$ and $P_2=〈u_1,u_2,u_3,\dots ,u_n〉$ be two hamiltonian paths of $G$. We say that $P_1$ and $P_2$ are independent if $u_1=v_1,u_n=v_n$, and $u_i\ne v_i$ for $1<i<n$. We say a set of hamiltonian paths $P_1,P_2,\dots ,P_s$ of $G$ between two distinct vertices are mutually independent if any two distinct paths in the set are independent. We use $n$ to denote the number of vertices and use $e$ to denote the number of edges in graph $G$. Moreover, we use $\bar{e}$ to denote the number of edges in the complement of $G$. Suppose that $G$ is a graph with $\bar{e}\le n-4$ and $n\ge 4$. We prove that there are at least $n-2-\bar{e}$ mutually independent hamiltonian paths between any pair of distinct vertices of $G$ except $n=5$ and $\bar{e}=1$. Assume that $G$ is a graph with the degree sum of any two non-adjacent vertices being at least $n+2$. Let $u$ and $v$ be any two distinct vertices of $G$. We prove that there are ${deg}_G\left(u\right)+{deg}_G\left(v\right)-n$ mutually independent hamiltonian paths between $u$ and $v$ if $(u,v)\in E\left(G\right)$ and there are ${deg}_G\left(u\right)+{deg}_G\left(v\right)-n+2$ mutually independent hamiltonian paths between $u$ and $v$ if otherwise.