In this paper, we develop a polynomial time algorithm to determine the cyclic edge connectivity of a \(k\)-regular graph for \(k \geq 3\). The time complexity of the algorithm is bounded by \(O(k^{11}|V|^8)\), in particular, it is \(O(|V|^8)\) for cubic graphs.

For each integer \(m \geq 1\), consider the graph \(G_m\) whose vertex set is the set \(\mathbb{N} = \{0,1,2,\ldots\}\) of natural numbers and whose edges are the pairs \(xy\) with \(y = x+m\), \(y = x-m\), \(y = mx\), or \(y = \frac{x}{m}\). Our aim in this note is to show that, for each \(m\), the graph \(G_m\) contains a Hamilton path. This answers a question of Lichiardopol.

Given a partial \(K_4\)-design \((X, {P})\), if \(x \in X\) is a vertex which occurs in exactly one block of \({P}\), then call \(x\) a free vertex. In this paper, a technique is described for obtaining a cubic embedding of any partial \(K_4\)-design with the property that every block in the partial design contains at least two free vertices.

The average distance \(\mu(D)\) of a strong digraph \(D\) is the average of the distances between all ordered pairs of distinct vertices of \(D\). Plesnik \([6]\) proved that if \(D\) is a strong tournament of order \(n\), then \(\mu(D) \leq \frac{n+4}{6} + \frac{1}{n}\). In this paper, we show that if \(D\) is a \(k\)-connected tournament of order \(n\), then \(\mu(D) \leq \frac{n}{6k} + \frac{19}{6} + \frac{k}{n}\). We demonstrate that, apart from an additive constant, this bound is best possible.

A subset \(U\) of a set \(S\) with a binary operation is called avoidable if \(S\) can be partitioned into two subsets \(A\) and \(B\) such that no element of \(U\) can be written as a product of two distinct elements of \(A\) or as the product of two distinct elements of \(B\). The avoidable sets of the bicyclic inverse semigroup are classified.

Let \(\alpha, \beta\) be any numbers. Given an initial sequence \(a_{0,m}\) (\(m = 0,1,2,\ldots\)), define the sequences \(a_{n,m}\) (\(n \geq 1\)) recursively by

\[a_{n,m} = \alpha a_{n-1,m} + \beta a_{n-1,m+1}; \quad \text{for n} \geq 1, m \geq 0.\]

Let \(\alpha, \beta\) be any numbers. Given an initial sequence \(a_{0,m}\) (\(m = 0,1,2,\ldots\)), define the sequences \(a_{n,m}\) (\(n \geq 1\)) recursively by

\[a_{n,m} = \alpha a_{n-1,m} + \beta a_{n-1,m+1}; \quad \text{for n} \geq 1, m \geq 0.\]

We call the matrix \((a_{n,m})_{n,m\geq 0}\) an generalized Seidel matrix with a parameter pair \((\alpha, \beta)\). If \(\alpha = \beta = 1\), then this matrix is the classical Seidel matrix. For various different parameter pairs \((\alpha, \beta)\) we will impose some evenness or oddness conditions on the exponential generating functions of the initial sequence \(a_{0,m}\) and the final sequence \(a_{n,0}\) of a generalized Seidel matrix (i.e., we require that these generating functions or certain related functions are even or odd). These conditions imply that the initial sequences and final sequences are equal to well-known classical sequences such as those of the Euler numbers, the Genocchi numbers, and the Springer numbers.

As applications, we give a straightforward proof of the continued fraction representations of the ordinary generating functions of the sequence of Genocchi numbers. And we also get the continued fractions representations of the ordinary generating functions of the Genocchi polynomials, Bernoulli polynomials, and Euler polynomials. Lastly, we give some applications of congruences for the Euler polynomials.

Let \(G\) be a simple graph with vertex set \(V\) and edge set \(E\). A vertex labeling \(f: V \to \{0,1\}\) induces an edge labeling \(\overline{f}: E \to \{0,1\}\) defined by \(\overline{f}(uv) = |f(u) – f(v)|\). Let \(v_f(0), v_f(1)\) denote the number of vertices \(v\) with \(f(v) = 0\) and \(f(v) = 1\) respectively. Let \(e_f(0), e_f(1)\) be similarly defined. A graph is said to be cordial if there exists a vertex labeling \(f\) such that \(|v_f(0) – v_f(1)| \leq 1\) and \(|e_f(0) – e_f(1)| \leq 1\).

In this paper, we give necessary and sufficient conditions for the cordiality of the \(t\)-ply \(P_t(u,v)\), i.e. a thread of ply number \(t\).

A Jacobi polynomial was introduced by Ozeki. It corresponds to the codes over \(\mathbb{F}_2\). Later, Bannai and Ozeki showed how to construct Jacobi forms with various index using a Jacobi polynomial corresponding to the binary codes. It generalizes Broué-Enguehard map. In this paper, we study Jacobi polynomial which corresponds to the codes over \(\mathbb{F}_{2f}\). We show how to construct Jacobi forms with various index over the totally real field. This is one of extension of Broué-Enguehard map.

The paper contains two main results. First, we obtain the chromatic polynomial on the \(n \times m\) section of the square lattice, solving a problem proposed by Read and Tutte \([5]\), the chromatic polynomial of the bracelet square lattice, and we find a recurrent-constructive process for the matrices of the \(k\)-colourings. The key concept for obtaining the inductive method is the compatible matrix.

Our second main result deals with the compatible matrix as the adjacency matrix of a graph. This represents a family of graphs, which is described.

Let \(G = (V, E)\) be a simple graph. For any real valued function \(f: V \to \mathbb{R}\), the weight of \(f\) is defined as \(f(V) = \sum f(v)\), over all vertices \(v \in V\). For positive integer \(k\), a total \(k\)-subdominating function (TkSF) is a function \(f: V \to \{-1,1\}\) such that \(f(N(v)) \geq k\) for at least \(k\) vertices \(v\) of \(G\). The total \(k\)-subdomination number \(\gamma^t_{ks}(G)\) of a graph \(G\) equals the minimum weight of a TKSF on \(G\). In the special case where \(k = |V|\), \(\gamma^t_{ks}(G)\) is the signed total domination number \([5]\). We research total \(k\)-subdomination numbers of some graphs and obtain a few lower bounds of \(\gamma^t_{ks}(G)\).

A convex hull of a set of points \(X\) is the minimal convex set containing \(X\). A box \(B\) is an interval \(B = \{x | x \in [a,b], a,b \in \mathbb{R}^n\}\). A box hull of a set of points \(X\) is defined to be the minimal box containing \(X\). Because both convex hulls and box hulls are closure operations of points, classical results for convex sets can naturally be extended for box hulls. We consider here the extensions of theorems by Carathéodory, Helly, and Radon to box hulls and obtain exact results.

The point-distinguishing chromatic index of a graph \(G = (V, E)\) is the smallest number of colors assigned to \(E\) so that no two different points are incident with the same color set. In this paper, we discuss the bounds of the point-distinguishing chromatic indices of graphs resulting from the graph operations. We emphasize that almost all of these bounds are best possible.

If \(G\) is a bipartite graph with bipartition \((X,Y)\), a subset \(S\) of \(X\) is called a one-sided dominating set if every vertex \(y \in Y\) is adjacent to some \(x \in S\). If \(S\) is minimal as a one-sided dominating set (i.e., if it has no proper subset which is also a one-sided dominating set), it is called a bipartite dominating set (see \([4], [5]\), and \([6]\)). We study bipartite dominating sets in hypercubes.

Let \(u,v\) be distinct vertices of a multigraph \(G\) with degrees \(d_u\) and \(d_v\), respectively. The number of edge-disjoint \(u,v\)-paths in \(G\) is bounded above by \(\min\{d_u,d_v\}\). A multigraph \(G\) is optimally edge-connected if for all pairs of distinct vertices \(u\) and \(v\) this upper bound is achieved. If \(G\) is a multigraph with degree sequence \(D\), then we say \(G\) is a realisation of \(D\). We characterise degree sequences of multigraphs that have an optimally edge-connected realisation as well as those for which every realisation is optimally edge-connected.

The \(associated \;graph \;of\; a\) \((0,1)\)-\(matrix\) has as its vertex set the lines of the matrix with vertices adjacent whenever their lines intersect at \(a\) \(1\). This association relates the \((0,1)\)-matrix and bipartite graph versions of the König-Egervary Theorem. We extend this graph association to higher dimensional matrices. We characterize these graphs, modulo isolated vertices, using a coloring in which every path between each pair of vertices contains the same two colors. We rely on previous results about \(p\)-dimensional gridline graphs, where vertices are \(1\)’s in a higher dimensional matrix and vertices are adjacent whenever they are on a common line. Also important is the dual property that the doubly iterated clique graph of a diamond- and simplicial vertex-free graph is isomorphic to the original.

Since Cohen introduced the notion of competition graph in \(1968\), various variations have been defined and studied by many authors. Using the combinatorial properties of the adjacency matrices of digraphs, Cho \(et\; al\). \([2]\) introduced the notion of a \(m\)-step competition graph as a generalization of the notion of a competition graph. Then they \([3]\) computed the \(2\)-step competition numbers of complete graphs, cycles, and paths. However, it seems difficult to compute the \(2\)-step competition numbers even for the trees whose competition numbers can easily be computed. Cho \(et\; al\). \([1]\) gave a sufficient condition for a tree to have the \(2\)-step competition number two. In this paper, we show that this sufficient condition is also a necessary condition for a tree to have the \(2\)-step competition number two, which completely characterizes the trees whose \(2\)-step competition numbers are two. In fact, this result turns out to characterize the connected triangle-free graphs whose \(2\)-step competition numbers are two.

In this paper, we are interested in lexicographic codes which are greedily constructed codes. For an arbitrary length \(n\), we shall find the basis of quaternary lexicographic codes, for short, lexicodes, with minimum distance \(d_m = 4\). Also, using a linear nim sum of some bases (such a vector is called the testing vector), its decoding algorithm will be found.

A maximal-clique partition of a graph is a family of its maximal complete sub-graphs that partitions its edge set. Many graphs do not have a maximal-clique partition, while some graphs have more than one. It is harder to find graphs in which maximal-clique partitions have different sizes. \(L(K_5)\) is a well-known example. In \(1982\), Pullman, Shank, and Wallis \([9]\) asked if there is a graph with fewer vertices than \(L(K_5)\) with this property. This paper confirms that there is no such graph.

Can an arbitrary graph be embedded in Euclidean space so that the isometry group of its vertex set is precisely its graph automorphism group? This paper gives an affirmative answer, explores the number of dimensions necessary, and classifies the outerplanar graphs that have such an embedding in the plane.

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\).