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.