We give necessary and sufficient conditions for the decomposition of the complete graphs with multiple holes, \( K_n \setminus hK_v \), into the graph-pair of order \( 4 \).

A vertex cover of a graph \( G = (V, E) \) is a subset \( S \subseteq V \) such that every edge is incident with at least one vertex in \( S \), and \( \alpha(G) \) is the cardinality of a smallest vertex cover. Let \( \mathcal{T} \) be a collection of vertex covers, not necessarily minimum. We say \( \mathcal{T} \) is closed if for every \( S \in \mathcal{T} \) and every \( e \in E \) there is a one-to-one function \( f : S \to V \) such that (1) \(f(S)\) is a vertex cover,(2) for some \(s \in S\), \(\{s, f(s)\} = e\), (3)for each \(s\) in \(S\), either \(s = f(s)\) or \(s\) is adjacent to \(f(s)\), and (4) \(f(S) \in \mathcal{T}\).A set is an eternal vertex cover if and only if it is a member of some closed family of vertex covers. The cardinality of a smallest eternal vertex cover is denoted \( \alpha_m^\infty(G) \). Eternal total vertex covers are defined similarly, with the restriction that the cover must also be a total dominating set. The cardinality of a smallest eternal total vertex cover is denoted \( \alpha_{mt}^\infty(G) \). These three vertex cover parameters satisfy the relation \(\alpha(G) \leq \alpha_{m}^\infty(G) \leq \alpha_{mt}^\infty(G) \leq 2\alpha(G).\) We define a triple \( (p, q, r) \) of positive integers such that \( p \leq q \leq r \leq 2p \) to be feasible if there is a connected graph \( G \) such that \( \alpha(G) = p \), \( \alpha_{m}^\infty(G) = q \), and \( \alpha_{mt}^\infty(G) = r \). This paper shows all triples with the above restrictions are feasible if \( p \neq q \) or \( r \leq \frac{3p}{2} \) and conjectures that there are no feasible triples of the form \( (p, p, r) \) with \( r > \frac{3p}{2} \). The graphs with triple \( (p, p + 1, 2p) \) are characterized and issues related to the conjecture are discussed.

We study the area distribution of closed walks of length \( n \), starting and ending at the origin. The concept of algebraic area of a walk in the square lattice is slightly modified and the usefulness of this concept is demonstrated through a simple argument. The idea of using a generating function of the form \( (x + x^{-1} + y + y^{-1})^n \) to study these walks is then discussed from a special viewpoint. Based on this, a polynomial time algorithm for calculating the exact distribution of such walks for a given length is concluded. The presented algorithm takes advantage of the Chinese remainder theorem to overcome the problem of arithmetic with large integers. Finally, the results of the implementation are given for \( n = 32, 64, 128 \).

The Wiener polarity index of a graph \( G \) is the number of unordered pairs of vertices \( u, v \) such that the distance between \( u \) and \( v \) is three, which was introduced by Harold Wiener in 1947. A linear time algorithm for computing the Wiener polarity index of trees was described, and also an algorithm which computes the index \( W_p(G) \) for any given connected graph \( G \) on \( n \) vertices in time \( O(M(n)) \) was presented, where \( M(n) \) denotes the time necessary to multiply two \( n \times n \) matrices of small integers (which is currently known to be \( O(n^{2.376}) \)). In this paper, we establish one polynomial algorithm to calculate the value of the Wiener polarity index of a bipartite graph.

Rado numbers are closely related to Ramsey numbers, but pertaining to equations and integers instead of cliques within graphs. For every integer \( m \geq 3 \) and every integer \( c \), let the 2-color Rado number \( r(m,c) \) be the least integer, if it exists, such that for every 2-coloring of the set \( \{1,2,\ldots,r(m,c)\} \) there exists a monochromatic solution to the equation \(\sum_{i=1}^{m-1} x_i + c = x_m\) .The values of \( r(m,c) \) have been determined previously for nonnegative values of \( c \), as well as all values of \( m \) and \( c \) such that \( -m+2 < c < 0 \) and \( c < -(m-1)(m-2) \). In this paper, we find \( r(m,c) \) for the remaining values of \( m \) and \( c \).

This paper deals with the Orchard crossing number of some families of graphs which are based on cycles. These include disjoint cycles, cycles which share a vertex and cycles which share an edge. Specifically, we focus on the prism and ladder graphs.

Let \(i(G)\) be the number of isolated vertices in graph \(G\). The isolated toughness of \(G\) is defined as \(I(G) = +\infty\) if \(G\) is complete; \(I(G) = \text{min}\{|S|/i(G-S) : S \subseteq V(G), i(G-S) \geq 2\}\) otherwise. In this paper, we determine that \(G\) is a fractional \((g, f, n)\)-critical graph if \(I(G) \geq \frac{b^2 + bn – 1}{a}\) if \(b > a\); \(I(G) \geq b + n\) if \(a = b\).

Let \(\mathcal{C}\) be a finite family of boxes in \(\mathbb{R}^d\), \(d \geq 3\), with \(S = \cup\{C : C \in \mathcal{C}\}\) connected and \(p \in S\). Assume that, for every geodesic chain \(D\) of \(\mathcal{C}\)-boxes containing \(p\), each coordinate projection \(\pi(D)\) of \(D\) is staircase starshaped with \(\pi(p) \in \text{Ker}\ \pi(D)\). Then \(S\) is staircase starshaped and \(p \in \text{Ker}\ S\). For \(n\) fixed, \(1 \leq n \leq d-2\), an analogous result holds for composites of \(n\) coordinate projections of \(D\) into \((d-n)\)-dimensional flats.

Let \( T(G) \) and \(\text{bind}(G)\) be the tenacity and the binding number, respectively, of a graph \( G \). The inequality \( T(G) \geq \text{bind}(G) – 1 \) was derived by D. Moazzami in [11]. In this paper, we provide a stronger lower bound on \( T(G) \) that is best possible when \(\text{bind}(G) \geq 1\).

In this paper, we give a new look at Sears’ \({}_{3}\phi_{2}\) transformation formula via a discrete random variable. This interpretation may provide a method to calculate \({}_{3}\phi_{2}\) by Monte Carlo experiments.