In this note, we consider arithmetic properties of the function

\[K(n)=\frac{(2n)!(2n+2)!}{(n-1)!(n+1)!^2(n+2)!}\]

which counts the number of two-legged knot diagrams with one self-intersection and \(n-1\) tangencies. This function recently arose in a paper by Jacobsen and Zinn-Justin on the enumeration of knots via a transfer matrix approach. Using elementary number theoretic techniques, we prove various results concerning \(K(n)\), including the following:

1. \(K(n)\) is never odd,
2. \(K(n)\) is never a quadratic residue modulo \(3\), and
3. \(K(n)\) is never a quadratic residue modulo \(5\).

A Halin graph is a plane graph \(H = T \cup C\), where \(T\) is a tree with no vertex of degree two and at least one vertex of degree three or more, and \(C\) is a cycle connecting the pendant vertices of \(T\) in the cyclic order determined by the drawing of \(T\). In this paper we determine the list chromatic number, the list chromatic index, and the list total chromatic number (except when \(\Delta = 3\)) of all Halin graphs, where \(\Delta\) denotes the maximum degree of \(H\).

In \([4]\) Fan Chung Graham investigates the notion of graph labelings and related bandwidth and cutwidth of such labelings when the host graph is a path graph. Motivated by problems presented in \([4]\) and our investigation of designing efficient virtual path layouts for communication networks, we investigate in this note labeling methods on graphs where the host graph is not restricted to a particular kind of graph. In \([2]\) authors introduced a metric on the set of connected simple graphs of a given order which represents load on edges of host graph under some restrictions on bandwidth of such labelings. In communication networks this translates into finding mappings between guest graph and host graph in a way that minimizes the congestion while restricting the delay. In this note, we present optimal mappings between special \(n\)-vertex graphs in \(\mathcal{G}_n\), and compute their distances with respect to the metric introduced in \([2]\). Some open questions are also presented.

We discuss several equivalent definitions of matroids, motivated by the single forbidden minor of matroid basis clutters.

Babson and Steingrimsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. Subsequently, Claesson presented a complete solution for the number of permutations avoiding any single pattern of type \((1,2)\) or \((2,1)\). For eight of these twelve patterns the answer is given by the Bell numbers. For the remaining four the answer is given by the Catalan numbers.

In the present paper we give a complete solution for the number of permutations avoiding a pair of patterns of type \((1,2)\) or \((2,1)\). We also conjecture the number of permutations avoiding the patterns in any set of three or more such patterns.

Let \(k \geq 1\) be an integer and let \(G\) be a graph of order \(p\). A set \(S\) of vertices in a graph is a total \(k\)-dominating set if every vertex of \(G\) is within distance at most \(k\) from some vertex of \(S\) other than itself. The smallest cardinality of such a set of vertices is called the total \(k\)-domination number of the graph and is denoted by \(\gamma_k^t(G)\). It is well known that \(\gamma_k^t(G) \leq \frac{2p}{2k+1}\) for \(p \leq 2k + 1\). In this paper, we present a characterization of connected graphs that achieve the upper bound. Furthermore, we characterize the connected graph \(G\) with \(\gamma_k^t(G) + \gamma_k^t(\overline{G}) = \frac{2p}{2k+1} + 2\).

A rational number \(\frac{p}{q}\) is said to be a closest approximation to a given real number \(\alpha\) provided it is closer to \(\alpha\) than any other rational number with denominator at most \(q\). We determine the sequence of closest approximations to \(\alpha\), giving our answer in terms of the simple continued fraction expansion of \(\alpha\).

In [Kit1] Kitaev discussed simultaneous avoidance of two \(3\)-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. In three essentially different cases, the numbers of such \(n\)-permutations are \(2^{n-1}\), the number of involutions in \(S_n\), and \(2^{E_n}\), where \(E_n\) is the \(n\)-th Euler number. In this paper we give recurrence relations for the remaining three essentially different cases.

To complete the descriptions in [Kit3] and [KitMans], we consider avoidance of a pattern of the form \(x-y-z\) (a classical \(3\)-pattern) and beginning or ending with an increasing or decreasing pattern. Moreover, we generalize this problem: we demand that a permutation must avoid a \(3\)-pattern, begin with a certain pattern, and end with a certain pattern simultaneously. We find the number of such permutations in case of avoiding an arbitrary generalized \(3\)-pattern and beginning and ending with increasing or decreasing patterns.

A graph \(G\) is called integral or Laplacian integral if all the eigenvalues of the adjacency matrix \(A(G)\) or the Laplacian matrix \(Lap(G) = D(G) – A(G)\) of \(G\) are integers, where \(D(G)\) denotes the diagonal matrix of the vertex degrees of \(G\). Let \(K_{n,n+1} \equiv K_{n+1,n}\) and \(K_{1,p}[(p-1)K_p]\) denote the \((n+1)\)-regular graph with \(4n+2\) vertices and the \(p\)-regular graph with \(p^2 + 1\) vertices, respectively. In this paper, we shall give the spectra and characteristic polynomials of \(K_{n,n+1} \equiv K_{n+1,n}\) and \(K_{1,p}[(p-1)K_p]\) from the theory on matrices. We derive the characteristic polynomials for their complement graphs, their line graphs, the complement graphs of their line graphs, and the line graphs of their complement graphs. We also obtain the numbers of spanning trees for such graphs. When \(p = n^2 + n + 1\), these graphs are not only integral but also Laplacian integral. The discovery of these integral graphs is a new contribution to the search of integral graphs.

Balakrishnan et al. \([1, 2]\) have shown that every graph is a subgraph of a graceful graph and an elegant graph. Also Liu and Zhang \([4]\) have shown that every graph is a subgraph of a harmonious graph. In this paper we prove a generalization of these two results that any given set of graphs \(G_1,G_1,\ldots,G_i\) can be packed into a graceful/harmonious/elegant graph.