Let \(H = K_{k_1,k_2,\ldots,k_t}\) be a complete multipartite graph having \(t \geq 3\) parts. Extending the well-known result that a simple graph \(G\) or its complement, \({G}\), is connected, it is proved that in any coloring of the edges of \(H\) with two colors, blue and red, at least one of the subgraphs induced by the blue edges or by the red edges, is connected.

Given a collection of points in the plane, a circle is drawn around each point with radius equal to the smallest distance from that point to any other in the collection. The sphere-of-influence graph is the intersection graph of the open balls given by these circles. Any graph isomorphic to such a graph is a SIG realizable in a plane. Similarly, one can define a SIG realizable on a sphere by selecting a collection of points on a sphere. We show that \(K_9\) is realizable as a SIG on a sphere and that the family of graphs realizable as SIGs on a sphere is at least as large as the family of SIGs in the plane.

In this paper, we construct many Hadamard matrices of order \(44\) and we use a new efficient algorithm to investigate the lower bound of inequivalent Hadamard matrices of order \(44\). Using four \((1, -1)\)-circulant matrices of order \(11\) in the Goethals-Seidel array, we obtain many new Hadamard matrices of order \(44\) and we show that there are at least \(6018\) inequivalent Hadamard matrices for this order. Moreover, we use a known method to investigate the existence of double even self-dual codes \([88, 44, d]\) over \(\text{GF}(2)\) constructed from these Hadamard matrices.

Given positive integers \(m, k,\) and \(t\). Let \(D_{m,[k,k+i]} = \{1,2,\ldots,m\} – \{k,k+1,\ldots,k+i\}\). The distance graph \(G(\mathbb{Z}, D_{m,[k,k+i]})\) has vertex set all integers \(\mathbb{Z}\) and edges connecting \(j\) and \(j’\) whenever \(|j-j’| \in D_{m,[k,k+i]}\). The fractional chromatic number, the chromatic number, and the circular chromatic number of \(G(\mathbb{Z}, D_{m,k,i})\) are denoted by \(\chi_f(\mathbb{Z}, D_{m[k,k+i]}), \chi(\mathbb{Z}, D_{m,[k,k+i]}),\) and \(\chi_c(\mathbb{Z}, D_{m,[k,k+i]})\), respectively. For \(i=0\), we simply denote \(D_{m,[k,k+0]}\) by \(D_{m,k}\). \(X(\mathbb{Z}, D_{m,k})\) was studied by Eggleton, Erdős and Skilton [5], Kemnitz and Kolberg [8], and Liu [9], and was completely solved by Chang, Liu and Zhu [1] who also determined \(\chi_c(\mathbb{Z}, D_{m,k})\) for any \(m\) and \(k\). The value of \(\chi_c(\mathbb{Z}, D_{m,k})\) was studied by Chang, Huang and Zhu [2] who finally determined \(\chi_c(\mathbb{Z}, D_{m,k})\) for any \(m\) and \(k\). This paper extends the study of \(G(\mathbb{Z}, D_{m,[k,k+i]})\) to values \(i\) with \(1 \leq i \leq k-1\). We completely determine \(\chi_f(\mathbb{Z}, D_{m,[k,k+i]})\) and \(\chi(\mathbb{Z}, D_{m,k,i})\) for any \(m\) and \(k\) with \(1 \leq i \leq k-1\). However, for \(\chi_c(\mathbb{Z}, D_{m,[k,k+i]})\), only some special cases are determined.

We introduce graphs \(G\) with at least one maximum independent set of vertices \(I\), such that \(\forall v \in V(G) \setminus I\), the number of vertices in \(N_G(v) \cap I\) is constant. When this number of vertices is equal to \(\lambda\), we say that \(I\) has the \(\lambda\)-property and that \(G\) is \(\lambda\)-regular-stable. Furthermore, we extend the study of this property to the well-covered graphs (that is, graphs where all maximal independent sets of vertices have the same cardinality). In this study, we consider well-covered graphs for which all maximal independent sets of vertices have the \(\lambda\)-property, herein called well-covered \(\lambda\)-regular-stable graphs.

Isometric subgraphs of hypercubes are known as partial cubes. Edge-critical partial cubes are introduced as the partial cubes \(G\) for which \(G – e\) is not a partial cube for any edge \(e\) of \(G\). An expansion theorem is proved by means of which one can generate many edge-critical partial cubes. Edge-critical partial cubes are characterized among the Cartesian product graphs. We also show that the \(3\)-cube and the subdivision graph of \(K_4\) are the only edge-critical partial cubes on at most \(10\) vertices.

This paper discusses the enumeration of rooted labelled spanning forests of the complete bipartite graph \(K_{m,n}\).

A set of edges \(D\) in a graph \(G\) is a dominating set of edges if every edge not in \(D\) is adjacent to at least one edge in \(D\). The minimum cardinality of an edge dominating set of \(G\) is the edge domination number of \(G\), denoted by \(D_E(G)\). In this paper, we investigate the edge domination number for the cartesian product of an \(n\)-colorable graph \(G\) and the complete graph \(K_n\).

For graph \(G\) with non-empty edge set, a \((j,k)\)-edge labeling of \(G\) is an integer labeling of the edges such that adjacent edges receive labels that differ by at least \(j\), and edges which are distance two apart receive labels that differ by at least \(k\). The \(\lambda’_{j,k}\)-number of \(G\) is the minimum span over the \((j,k)\)-edge labelings of \(G\). By establishing the equivalence of the edge labelings of \(G\) to particular vertex labelings of \(G\) and the line graph of \(G\), we explore the properties of \(\chi_{j,k}(G)\). In particular, we obtain bounds on \(\lambda’_{j,k}(G)\), and prove that the \(\Delta^2\) conjecture of Griggs and Yeh is true for graph \(H\) if \(H\) is the line graph of some graph \(G\). We investigate the \(\lambda’_{1,1}\)-numbers and \(\lambda_{2,1}\)-numbers of common classes of graphs, including complete graphs, trees, \(n\)-cubes, and joins.

The \(n \times n\) Lah matrix \(L_n\) is defined by \((L_n)_{ij} = l(i, j)\), where \({l}(i, j)\) is the unsigned Lah number. In this paper, we investigate the algebraic properties of \(L_n\), and many important relations between \({L}_n\) and Pascal matrix and Stirling matrix, respectively. In addition, we obtain its exponential expansion and Pascal matrix factorization. Furthermore, we introduce a simple method to find and prove combinatorial identities.