Given a graph \( G \), we show how to compute the number of (perfect) matchings in the graphs \( G \Box P_n \) and \( G \Box C_n \), by looking at appropriate entries in a power of a particular matrix. We give some generalizations and extensions of this result, including showing how to compute tilings of \( k \times n \) boards using monomers, dimers, and \( 2 \times 2 \) tiles.

Consider a simple undirected graph \( G = (V, E) \). A family of subtrees, \(\{T_v\}_{v \in V}\), of a tree \(\mathcal{T}\) is called a \((\mathcal{T}; t)\)-representation of \(G\) provided \( uv \in E \) if and only if \( |T_u \cap T_v| \geq t \). In this paper, we consider \((\mathcal{T}; t)\)-representations for graphs containing large asteroidal sets, where \(\mathcal{T}\) is a subdivision of the \(n\)-star \(K_{1, n}\). An asteroidal set in a graph \(G\) is a subset \(A\) of the vertex set such that for all 3-element subsets of \(A\), there exists a path in \(G\) between any two of these vertices which avoids the neighborhood of the third vertex. We construct a representation of an asteroidal set of size \( n + \sum_{k=2}^{n} \binom{n}{k} \binom{t-2}{k-1} \) and show that no graph containing a larger asteroidal set can be represented.

A set \( S \) of vertices in a graph \( G \) is a total dominating set of \( G \) if every vertex of \( G \) is adjacent to some vertex in \( S \). The minimum cardinality of a total dominating set of \( G \) is the total domination number of \( G \). We study graphs having the same total domination number as their complements. In particular, we characterize the cubic graphs having this property. Also, we characterize such graphs with total domination numbers equal to two or three, and we determine properties of the ones with larger total domination numbers.

In 1991 Gnanajothi conjectured: Each tree is odd-graceful. In this paper, we define the edge-ordered odd-graceful labeling of trees and show the odd-gracefulness of all symmetric trees.

A method is suggested for the construction of quadrangulations of the closed orientable surface with given genus \( g \) and either (1) with a given chromatic number or (2) with a given order allowed by the genus \( g \). In particular, N. Hartshfield and G. Ringel’s results [J. Comb. Theory, Ser. B 46 (1989), 84-95] are generalized by way of generating minimal quadrangulations of infinitely many other genera.

For integers \( s, t \geq 1 \), the Ramsey number \( R(s, t) \) is defined to be the least positive integer \( n \) such that every graph on \( n \) vertices contains either a clique of order \( s \) or an independent set of order \( t \). In this note, the lower bound for the Ramsey number \( R(7, 9) \) is improved from \( 241 \) to \( 242 \). The new bound is obtained by searching the maximum common induced subgraph between two graphs with a depth variable local search technique.

In this paper, we give an alternative and more intuitive proof to one of two classic inequalities given by Diaconis and Graham in 1977. The inequality involves three metrics on the symmetric group, i.e., the set of all permutations of the first \( n \) positive integers. Our technique for the proof of the inequality allows us to resolve an open problem posed in that paper: When does equality hold? It also allows us to estimate how often equality holds. In addition, our technique can sometimes be applied for the proof of other inequalities between metrics or pseudo-metrics on the symmetric group.

Pooling designs are standard experimental tools in many biotechnical applications. In this paper, we construct a family of error-correcting pooling designs with the incidence matrix of two types of subspaces of singular linear space over finite fields, and exhibit their disjunct properties.

Let \( S \) be an orthogonal polygon in the plane, bounded by a simple closed curve, and let \( R \) be the smallest rectangular region containing \( S \). Assume that \( S \) is star-shaped via staircase paths. For every point \( p \) in \( \mathbb{R}^2 \setminus (\text{int} \, S) \), there is a corresponding point \( q \) in \( \text{bdry} \, S \) such that \( p \) lies in a maximal staircase convex cone \( C_q \) at \( q \) in \( \mathbb{R}^2 \setminus (\text{int} \, S) \). Furthermore, point \( q \) may be selected to satisfy these requirements:

1. If \( p \in \mathbb{R}^2 \setminus (\text{int} \, R) \), then \( q \) is an endpoint of an extreme edge of \( S \).
2. If \( p \in (\text{int} \, R) \setminus (\text{int} \, S) \), then \( q \) is a point of local nonconvexity of \( S \) and \( C_q \) is unique. Moreover, there is a neighborhood \( N \) of \( q \) such that, for \( s \) in \( (\text{bdry} \, S) \cap N \) and for \( C_s \) any staircase cone at \( s \) in \( \mathbb{R}^2 \setminus (\text{int} \, S) \), \( C_s \subseteq C_q \).

Thus we obtain a finite family of staircase convex cones whose union is \( \mathbb{R}^2 \setminus (\text{int} \, S) \).

If there are integers \( k \) and \( \lambda \neq 0 \) such that a total labeling \( f \) of a connected graph \( G = (V, E) \) from \( V \cup E \) to \( \{1, 2, \ldots, |V| + |E|\} \) satisfies \( f(x) \neq f(y) \) for distinct \( x, y \in V \cup E \) and

\[ f(u) + f(v) = k + \lambda f(uv) \]

for each edge \( uv \in E \), then \( f \) is called a \( (k, \lambda) \)-\({magically\; total\; labeling}\) (\( (k, \lambda) \)-\({mtl}\) for short) of \( G \). Several properties of \( (k, \lambda) \)-\({mtls}\) of graphs are shown. The sufficient and necessary connections between \( (k, \lambda) \)-\emph{mtls} and several known labelings (such as graceful, odd-graceful, felicitous, and \( (b, d) \)-edge antimagic total labelings) are given. Furthermore, every tree is proven to be a subgraph of a tree having super \( (k, \lambda) \)-\({mtls}\).