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.