This note proves that, given one member, \(T\), of a particular family of radius-three trees, every radius-two, triangle-free graph, \(G\), with large enough chromatic number contains an induced copy of \(T\).

Let \(k(D)\) be the index of convergence of a digraph \(D\) of order \(n \geq 8\). It is proved that if \(D\) is not strong with only minimally strong components and the greatest common divisor of the cycle lengths of \(D\) is at least two, then

\[k(D) \leq \begin{cases}
\frac{1}{2}(n^2 – 8n + 24) & \text{if } n \text{ is even}, \\
\frac{1}{2}(n^2 – 10n + 35) & \text{if } n \text{ is odd}.
\end{cases}\]

The cases of equality are also characterized.

Let \(C_n\) denote the cycle with \(n\) vertices, and \(C_n^{(t)}\) denote the graphs consisting of \(t\) copies of \(C_n\), with a vertex in common. Koh et al. conjectured that the graphs \(C_n^{(t)}\) are graceful if and only if \(nt \equiv 0, 3 \pmod{4}\). The conjecture has been shown true for \(n = 3, 5, 6, 4k\). In this paper, the conjecture is shown to be true for \(n = 7\).

It is well known that a linear code over a finite field with the systematic generator matrix \([I | P]\) is MDS (Maximum Distance Separable) if and only if every square submatrix of \(P\) is nonsingular. In this correspondence, we obtain a similar characterization for the class of Near-MDS codes in terms of the submatrices of \(P\).

In this paper, we define the signed total domatic number of a graph in an analogous way to that of the fractional domatic number defined by Rall (A fractional version of domatic number. Congr. Numer. \(74 (1990), 100-106)\). A function \(f: V(G) \to \{-1,1\}\) defined on the vertices of a graph \(G\) is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A set \(\{f_1,\ldots,f_a\}\) of signed total dominating functions on \(G\) such that \(\sum\limits_{i=1}^a f_i(v) \leq 1\) for each vertex \(v \in V(G)\) is called a signed total dominating family of functions on \(G\). The signed total domatic number of \(G\) is the maximum number of functions in a signed total dominating family of \(G\). In this paper, we investigate the signed total domatic number for special classes of graphs.

Let \(G\) be the product of two directed cycles, let \(Z_a\) be a subgroup of \(Z_a\), and let \(Z_d\) be a subgroup of \(Z_b\). Also, let \(A = \frac{a}{c}\) and \(B = \frac{b}{d}\). We say that \(G\) is \((Z_c \times Z_d)\)-hyperhamiltonian if there is a spanning connected subgraph of \(G\) that has degree \((2, 2)\) at the vertices of \(Z_c \times Z_d\) and degree \((1, 1)\) everywhere else. We show that the graph \(G\) is \((Z_c \times Z_d)\)-hyperhamiltonian if and only if there exist positive integers \(m\) and \(n\) such that \(Am + Bn = AB + 1\), \(gcd(m, n) = 1\) or \(2\), and when \(gcd(m, n) = 2\), then \(gcd(dm, cn) = 2\).

In this paper, it is shown that a partial edge-disjoint decomposition of \(K_{n}\) into kites (that is, into copies of \(K_3\) with a pendant edge attached) can be embedded in a complete edge-disjoint decomposition of \(K_{4t+9}\) into kites for all even \(t \geq 2n\). The proof requires first proving another interesting result, a generalization of an embedding result on symmetric latin squares by L. D. Andersen, following a result by A. Cruse.

Let \(T_n\) be the complete binary tree of height \(n\) considered as the Hasse-diagram of a poset with its root \(1_n\) as the maximum element. For a tree or forest \(T\), we count the embeddings of \(T\) into \(T_n\) as posets by the functions \(A(n;T) = |\{S \subseteq T_n : 1_n \in S, S \cong T\}|\), and \(B(n;T) = |\{S \subseteq T_n : 1_n \notin S, S \cong T\}|\). Here we summarize what we know about the ratio \(A(n;T)/B(n;T)\), in case of \(T\) being a chain or an antichain.

In this paper, the concept of clique number of uniform hypergraph is defined and its relationship with circular chromatic number and clique number is studied. For every positive integer \(k, p\) and \(q\), \(2q \leq p\) we construct a \(k\)-uniform hypergraph with small clique number whose circular chromatic number is equal to \(\frac{p}{q}\). We define the concept and study the properties of \(c\)-perfect \(k\)-uniform hypergraphs.

Given a connected graph \(G\) and a subset \(S\) of vertices, the Steiner distance of \(S\) in \(G\) is the minimum number of edges in a tree in \(G\) that contains all of \(S\). Given a positive integer \(m\), let \(\mu_m(G)\) denote the average Steiner distance over all sets \(S\) of \(m\) vertices in \(G\). In particular, \(\mu_2(G)\) is just the average distance of \(G\), often denoted by \(\mu(G)\). Dankelmann, Oellermann, and Swart \([1]\) conjectured that if \(G\) is a connected graph of order \(n\) and \(3 \leq m \leq n\), then \(\frac{\mu_m(G)}{\mu(G)} \geq 3(\frac{m-1}{m+1})\). In this note, we disprove their conjecture by showing that

\[\lim_{m \to \infty} inf \{ \frac{\mu_m(G)}{\mu(G)} :G \text{ is connected and $n(G)\geq m$} \} = 2.\]

Given a simple graph \(G\) on \(n\) vertices, let \(\sigma_2(G)\) be the minimum sum of the degrees of any two non-adjacent vertices. The graph \(G\) is said to be connected if any two distinct vertices may be joined by a path. It is easy to see that if \(\sigma_2(G) \geq n-1\) then \(G\) is not only connected, but we can choose the connecting path to be of size at most two. Ore \([4]\) proved that if \(\sigma_2(G) \geq n+1\) we may always choose this path to cover all the vertices of \(G\). In this paper we extend these results to systems of vertex disjoint paths connecting two vertex \(k\)-sets of \(G\).

A graph with vertex set \(V\) is said to have a prime labeling if its vertices are labelled with distinct integers from \(\{1, 2, \ldots, |V|\}\) such that for each edge \(xy\), the labels assigned to \(x\) and \(y\) are relatively prime. A graph that admits a prime labeling is called a prime graph. It has been conjectured \([1]\) that when \(n\) is a prime integer and \(m < n\), the planar grid \(P_m \times P_n\) is prime. We prove the conjecture and also that \(P_n \times P_n\) is prime when \(n\) is a prime integer.

The exact values of eleven Ramsey numbers \(r(K_{l_1,n_1} , K_{l_2, n_2})\) where \(3 \leq l_1+n_1, l_2+n_2 \leq 7\) are determined, almost completing the table of all \(66\) such numbers.

In \([1]\) and \([4]\), the authors derive Fermat’s (little), Lucas’s and Wilson’s theorems, among other results, all from a single combinatorial lemma. This lemma can be derived by applying Burnside’s theorem to an action by a cyclic group of prime order. In this note, we generalize this lemma by applying Burnside’s theorem to the corresponding action by an arbitrary finite cyclic group. Although this idea is not new, by revisiting the constructions in \([1]\) and \([4]\) we derive three divisibility theorems for which the aforementioned classical theorems are, respectively, the cases of a prime divisor, and two of these generalizations are new. Throughout, \(n\) and \(p\) denote positive integers with \(p\) prime and \(\mathbb{Z}_n\) denotes the cyclic group of integers under addition modulo \(n\).

Working on the problem of finding the numbers of lattice points inside convex lattice polygons, Rabinowitz has made several conjectures dealing with convex lattice nonagons and decagons. An intensive computer search preceded a formulation of the conjectures. The main purpose of this paper is to prove some of Rabinowitz’s conjectures. Moreover, we obtain an improvement of a conjectured result and give short proofs of two known results.

Let \(k \geq 1\) be an integer and let \(G = (V, E)\) be a graph. A set \(S\) of vertices of \(G\) is \(k\)-independent if the distance between any two vertices of \(S\) is at least \(k+1\). We denote by \(\rho_k(G)\) the maximum cardinality among all \(k\)-independent sets of \(G\). Number \(\rho_k(G)\) is called the \(k\)-packing number of \(G\). Furthermore, \(S\) is defined to be \(k\)-dominating set in \(G\) if every vertex in \(V(G) – S\) is at distance at most \(k\) from some vertex in \(S\). A set \(S\) is \(k\)-independent dominating if it is both \(k\)-independent and \(k\)-dominating. The \(k\)-independent dominating number, \(i_k(G)\), is the minimum cardinality among all \(k\)-independent dominating sets of \(G\). We find the values \(i_k(G)\) and \(\rho_k(G)\) for iterated line graphs.

The maximum genus, a topological invariant of graphs, was inaugurated by Nordhaus \(et\; al\). \([16]\). In this paper, the relations between the maximum non-adjacent edge set and the upper embeddability of a graph are discussed, and the lower bounds on maximum genus of a graph in terms of its girth and maximum non-adjacent edge set are given. Furthermore, these bounds are shown to be best possible. Thus, some new results on the upper embeddability and the lower bounds on the maximum genus of graphs are given.

The problem of monitoring an electric power system by placing as few measurement devices in the system as possible is closely related to the well known vertex covering and dominating set problems in graphs (see SIAM J. Discrete Math. \(15(4) (2002), 519-529)\). A set \(S\) of vertices is defined to be a power dominating set of a graph if every vertex and every edge in the system is monitored by the set \(S\) (following a set of rules for power system monitoring). The minimum cardinality of a power dominating set of a graph is its power domination number. We investigate the power domination number of a block graph.

A \((p,q)\)-graph \(G\) in which the edges are labeled \(1,2,3,\ldots,q\) so that the vertex sums are constant, is called supermagic. If the vertex sum mod \(p\) is a constant, then \(G\) is called edge-magic. We investigate the supermagic characteristic of a simple graph \(G\), and its edge-splitting extension \(SPE(G,f)\). The construction provides an abundance of new supermagic multigraphs.

The basis number of a graph \(G\) is defined to be the least integer \(k\) such that \(G\) has a \(k\)-fold basis for its cycle space. We investigate the basis number of the composition of theta graphs, a theta graph and a path, a theta graph and a cycle, a path and a theta graph, and a cycle and a theta graph.

We introduce certain types of surfaces \(M_j^n\), for \(j = 1,2,\ldots,11\) and determine their genus distributions. At the basis of joint trees introduced by Liu, we develop the surface sorting method to calculate the embedding distribution by genus.

Network reliability is an important issue in the area of distributed computing. Most of the early work in this area takes a probabilistic approach to the problem. However, sometimes it is important to incorporate subjective reliability estimates into the measure. To serve this goal, we propose the use of the weighted integrity, a measure of graph vulnerability. The weighted integrity problem is known to be NP-complete for most of the common network topologies including tree, mesh, hypercube, etc. It is known to be NP-complete even for most perfect graphs, including comparability graphs and chordal graphs. However, the computational complexity of the problem is not known for one class of perfect graphs, namely, co-comparability graphs. In this paper, we give a polynomial-time algorithm to compute the weighted integrity of interval graphs, a subclass of co-comparability graphs.

The vertex linear arboricity \(vla(G)\) of a graph \(G\) is the minimum number of subsets into which the vertex set \(V(G)\) can be partitioned so that each subset induces a subgraph whose connected components are paths. An integer distance graph is a graph \(G(D)\) with the set of all integers as vertex set and two vertices \(u,v \in {Z}\) are adjacent if and only if \(|u-v| \in D\) where the distance set \(D\) is a subset of the positive integers set. Let \(D_{m,k} = \{1,2,\ldots,m\} – \{k\}\) for \(m > k \geq 1\). In this paper, some upper and lower bounds of the vertex linear arboricity of the integer distance graph \(G(D_{m,k})\) are obtained. Moreover, \(vla(G(D_{m,1})) = \lceil \frac{m}{4} \rceil +1\) for \(m \geq 3\), \(vla(G(D_{8l+1,2})) = 2l + 2\) for any positive integer \(l\) and \(vla(G(D_{4q,2})) = q+2\) for any integer \(q \geq 2\).

We determine all spreads of symmetry of the dual polar space \(H^D(2n-1,q^2)\). We use this to show the existence of glued near polygons of type \(H^D(2n_1-1,q^2) \otimes H^D(2n_2-1,q^2)\). We also show that there exists a unique glued near polygon of type \(H^D(2n_1-1,4) \otimes H^D(2n_2-1,4)\) for all \(n_1,n_2 \geq 2\). The unique glued near polygon of type \(H^D(2n-1,4) \otimes Q(2n_2-1,q^2)\) has the property that it contains \(H^D(2n-1,4)\) as a big geodetically closed sub near polygon. We will determine all dense near \((2n+2)\)-gons, \(n \geq 3\), which have \(H^D(2n-1,4)\) as a big geodetically closed sub near polygon. We will prove that such a near polygon is isomorphic to either \(H^D(2n+1,4)\), \(H^D(2n-1,4) \otimes Q(5,2)\) or \(H^D(2n-1,4) \times L\) for some line \(L\) of size at least three.

Given a connected graph \(G\) and two vertices \(u\) and \(v\) in \(G\), \(I_G[u, v]\) denotes the closed interval consisting of \(u\), \(v\) and all vertices lying on some \(u\)–\(v\) geodesic of \(G\). A subset \(S\) of \(V(G)\) is called a geodetic cover of \(G\) if \(I_G[S] = V(G)\), where \(I_G[S] = \cup_{u,v\in S} I_G[u, v]\). A geodetic cover of minimum cardinality is called a geodetic basis. In this paper, we give the geodetic covers and geodetic bases of the composition of a connected graph and a complete graph.

Starlike graphs are the intersection graphs of substars of a star. We describe different characterizations of starlike graphs, including one by forbidden subgraphs. In addition, we present characterizations for a natural subclass of it, the starlike-threshold graphs.

We show that permutation decoding can be used, and give explicit PD-sets in the symmetric group, for some of the binary codes obtained from the adjacency matrices of the graphs on \(\binom{n}{3}\) vertices, for \(n \geq 7\), with adjacency defined by the vertices as \(3\)-sets being adjacent if they have zero, one or two elements in common, respectively.

In this paper, we have discussed the dynamic coloring of a kind of planar graph. Let \(G\) be a Pseudo-Halin graph, we prove that the dynamic chromatic number of \(G\) is at most \(4\). Examples are given to show the bounds can be attained.