The harmonic index \(H(G)\) of a graph \(G\) is defined as the sum of the weights \(\frac{2}{d_u+ d_v}\) of all edges \(uv\) of \(G\), where \(d_u\) denotes the degree of a vertex \(u\) in \(G\). We determine the \(n\)-vertex trees with the second and third maximum harmonic indices for \(n \geq 7\), the fourth maximum harmonic index for \(n \geq 10\), and fifth maximum harmonic index for $n \geq 11\), and unicyclic graphs with the second and third maximum harmonic indices for \(n \geq 5\), the fourth maximum harmonic index for \(n \geq 7\), and fifth maximum harmonic index for \(n \geq 8\), and bicyclic graphs with the maximum harmonic index for \(n \geq 6\), the second and third maximum harmonic indices for \(n \geq 7\), and fourth maximum harmonic index for \(n \geq 9\).

Graph embedding has been known as a powerful tool for implementation of parallel algorithms and simulation of different interconnection networks. In this paper, we obtain the minimum wirelength of embedding circulant networks into necklace and windmill graphs. The algorithms for obtaining the same are of \(O(2n)\)-linear time.

In this paper, a reliable symbolic computational algorithm is presented for inverting a general companion matrix by using parallel computing along with recursion. The computational cost of the algorithm is \(O(n^2)\). The algorithm is implementable to the Computer Algebra System (CAS) such as MAPLE, MATLAB, and MATHEMATICA. Three examples are presented for the sake of illustration.

Let \(K_r\) be the complete graph on \(r\) vertices in which there exists an edge between every pair of vertices, \(K_{m,n}\) be the complete bipartite graph with \(m\) vertices in one partition and \(n\) vertices in the other partition, where each vertex in one partition is adjacent to each vertex in the other partition, and \(K(n, r)\) be the complete \(r\)-partite graph \(K_{n,n,…,n}\) where each partition has \(n\) vertices. In this paper, we determine the minimum number of monochromatic stars \(K_{1,p}\), \( \forall p \geq 2\), in any \(t\)-coloring (\(t \geq 2\)) of edges of \(K_r\), \(K_{m,n}\), and \(K(n, r)\). Also, we prove that these lower bounds are sharp for all values of \(m, n, p, r\), and \(t\) by giving explicit constructions.

In this paper, we prove that if the toughness of a \(k\)-tree \(G\) is at least \(\frac{k+1}{3}\), then \(G\) is panconnected for \(k \geq 3\), or \(G\) is vertex pancyclic for \(k = 2\). This result improves a result of Broersma, Xiong, and Yoshimoto.

Since the Wiener index has been successful in the study of benzenoid systems and boiling points of alkanes, it is natural to examine this number for the study of fullerenes, most of whose cycles are hexagons. This topological index is equal to the sum of distances between all pairs of vertices of the respective graph. It was introduced in \(1947\) by one of the pioneers of this area, Harold Wiener, who realized that there are correlations between the boiling points of paraffins and the structure of the molecules. The present paper is the first attempt to compute the Wiener index of an infinite class of fullerenes. Further, we obtain a correlation between the values of the Wiener index and the boiling point of such fullerenes for the first time.

A graph is said to be symmetric if its automorphism group is transitive on its arcs. A complete classification is given of pentavalent symmetric graphs of order \(40p\) for each prime \(p\). It is shown that a connected pentavalent symmetric graph of order \(40p\) exists if and only if \(p = 3\), and up to isomorphism, there are only two such graphs.

A broadcast on a graph \(G\) is a function \(f: V \to \{0, \dots, diam(G)\}\) such that for every vertex \(v \in V(G)\), \(f(v) \leq e(v)\), where \(diam(G)\) denotes the diameter of \(G\) and \(e(v)\) denotes the eccentricity of vertex \(v\). The upper broadcast domination number of a graph is the maximum value of \(\sum_{v \in V} f(v)\) among all minimal broadcasts \(f\) for which each vertex of the graph is within distance \(f(v)\) from some vertex \(v\) having \(f(v) \geq 1\). We give a new upper bound on the upper broadcast domination number which improves a previous result of Dunbar et al. in [Broadcasts in graphs, Discrete Applied Mathematics 154 (2006) 59-75]. We also prove that the upper broadcast domination number of any grid graph \(G_{m,n} = P_m \Box P_n\) equals \(m(n – 1)\).

For a vertex \(v\) of a graph \(G\), Zhu, Li, and Deng introduced the concept of implicit degree \(id(v)\), according to the degrees of the neighbors of \(v\) and the vertices at distance \(2\) with \(v\) in \(G\). For a subset \(S \subseteq V(G)\), let \(i\Delta_2(G, S)\) denote the maximum value of the implicit degree sum of two vertices of \(S\). In this paper, we will prove: Let \(G\) be a \(2\)-connected graph on \(n \geq 3\) vertices and \(d\) be a nonnegative integer. If \(i\Delta_2(G, S) \geq d\) for each independent set \(S\) of order \(\kappa(G) + 1\), then \(G\) has a cycle of length at least \(\min\{d, n\}\).

For a nonempty graph \(G = (V(G), E(G))\), a signed cycle dominating function on \(G\) is introduced by Xu in 2009 as a function \(f : E(G) \to \{1, -1\}\) such that \(\sum_{e \in E(C)} f(e) \geq 1\) for any induced cycle \(C\) of \(G\). A set \(\{f_1, f_2, \dots, f_d\}\) of distinct signed cycle dominating functions on \(G\) with the property that \(\sum_{i=1}^{d} f_i(e) \leq 1\) for each \(e \in E(G)\), is called a signed cycle dominating family (of functions) on \(G\). The maximum number of functions in a signed cycle dominating family on \(G\) is the signed cycle domatic number of \(G\), denoted by \(d’_{sc}(G)\). In this paper, we study the signed cycle domatic numbers in graphs and present sharp bounds for \(d’_{sc}(G)\). In addition, we determine the signed cycle domatic number of some special graphs.