The Randić index \(R(G)\) of a graph \(G\) is the sum of the weights \((d_u d_v)^{-\frac{1}{2}}\) over all edges \(uv\) of \(G\), where \(d_u\) denotes the degree of the vertex \(u\). In this paper, we determine the first ten, eight, and six largest values for the Randić indices among all trees, unicyclic graphs, and bicyclic graphs of order \(n \geq 11\), respectively. These extend the results of Du and Zhou [On Randić indices of trees, unicyclic graphs, and bicyclic graphs, International Journal of Quantum Chemistry, 111 (2011), 2760–2770].

A paired-dominating set of a graph \(G\) is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number is the minimum cardinality of a paired-dominating set of \(G\). In this paper, we investigate the paired-domination number in claw-free graphs with minimum degree at least four. We show that a connected claw-free graph \(G\) with minimum degree at least four has paired-domination number at most \(\frac{4}{7}\) its order.

Given a set of vertices \(S = \{v_1, v_2, \ldots, v_k\}\) of a connected graph \(G\), the metric representation of a vertex \(v\) of \(G\) with respect to \(S\) is the vector \(r(v|S) = (d(v, v_1), d(v, v_2), \ldots, d(v, v_k))\), where \(d(v, v_i)\), \(i \in \{1, \ldots, k\}\), denotes the distance between \(v\) and \(v_i\). \(S\) is a resolving set of \(G\) if for every pair of distinct vertices \(u, v\) of \(G\), \(r(u|S) \neq r(v|S)\). The metric dimension \(\dim(G)\) of \(G\) is the minimum cardinality of any resolving set of \(G\). Given an ordered partition \(\Pi = \{P_1, P_2, \ldots, P_t\}\) of vertices of a connected graph \(G\), the partition representation of a vertex \(v\) of \(G\), with respect to the partition \(\Pi\), is the vector \(r(v|\Pi) = (d(v, P_1), d(v, P_2), \ldots, d(v, P_t))\), where \(d(v, P_i)\), \(1 \leq i \leq t\), represents the distance between the vertex \(v\) and the set \(P_i\), that is \(d(v, P_i) = \min_{u \in P_i} \{d(v, u)\}\). \(\Pi\) is a resolving partition for \(G\) if for every pair of distinct vertices \(u, v\) of \(G\), \(r(u|\Pi) \neq r(v|\Pi)\). The partition dimension \(\mathrm{pd}(G)\) of \(G\) is the minimum number of sets in any resolving partition for \(G\). Let \(G\) and \(H\) be two graphs of order \(n\) and \(m\), respectively. The corona product \(G \odot H\) is defined as the graph obtained from \(G\) and \(H\) by taking one copy of \(G\) and \(n\) copies of \(H\) and then joining, by an edge, all the vertices from the \(i\)-th copy of \(H\) with the \(i\)-th vertex of \(G\). Here, we study the relationship between \(\mathrm{pd}(G \odot H)\) and several parameters of the graphs \(G \odot H\), \(G\), and \(H\), including \(\dim(G \odot H)\), \(\mathrm{pd}(G)\), and \(\mathrm{pd}(H)\).

A bridge graph is a special one of those graphs with more than one cut-edge. In this paper, we compute Wiener, hyper-Wiener, \(PI\) and vertex \(PI\) indices of graphs with more than one cut-edge, which generalize results in [12, 13, 14].

For an ordered set \(W = \{w_1, w_2, \ldots, w_k\}\) of vertices and a vertex \(v\) in a connected graph \(G\), the ordered \(k\)-vector \(r(v|W) := (d(v, w_1), d(v, w_2), \ldots, d(v, w_k))\) is called the (metric) representation of \(v\) with respect to \(W\), where \(d(x, y)\) is the distance between the vertices \(x\) and \(y\). The set \(W\) is called a resolving set for \(G\) if distinct vertices of \(G\) have distinct representations with respect to \(W\). A minimum resolving set for \(G\) is a basis of \(G\) and its cardinality is the metric dimension of \(G\). The resolving number of a connected graph \(G\) is the minimum \(k\) such that every \(k\)-set of vertices of \(G\) is a resolving set. A connected graph \(G\) is called randomly \(k\)-dimensional if each \(k\)-set of vertices of \(G\) is a basis. In this paper, along with some properties of randomly \(k\)-dimensional graphs, we prove that a connected graph \(G\) with at least two vertices is randomly \(k\)-dimensional if and only if \(G\) is a complete graph \(K_{k+1}\) or an odd cycle.

We say that \(G\) is nearly claw-free if for every \(v \in A\), the set of centers of claws of \(G\), there exist two vertices \(x, y \in N(v)\) such that \(x, y \notin A\) and \(N_G(v) \subseteq N_G(x) \cup N_G(y) \cup \{x, y\}\). A graph \(G\) is triangularly connected if for every pair of edges \(e_1, e_2 \in E(G)\), \(G\) has a sequence of \(3\)-cycles \(C_1, C_2, \ldots, C_r\) such that \(e_1 \in C_1, e_2 \in C_l\) and \(E(C_i) \cap E(C_{i+1}) \neq \emptyset\) for \(1 \leq i \leq l-1\). In this paper, we will show that (i) every triangularly connected \(K_{1,4}\)-free nearly claw-free graph on at least three vertices is fully cycle extendable if the clique number of the subgraph induced by the set of centers of claws of \(G\) is at most \(2\), and (ii) every \(4\)-connected line graph of a nearly claw-free graph is hamiltonian connected.

In this paper, we will find a combinatorial formula that relates the power of a \(k\)-Fibonacci number, \(F_{k,n}^p\), to the number \(F_{k,an}\). From this formula, and if \(p\) is odd, we will find a new formula that allows expressing the \(k\)-Fibonacci number \(F_{k,(2r+1)n}\) as a combination of odd powers of \(F_{k,n}\). If \(p\) is even, the formula is similar but for the even \(k\)-Lucas numbers \(L_{k,2rn}\).

The resistance distance between two vertices of a connected graph \(G\) is defined as the effective resistance between them in the corresponding electrical network constructed from \(G\) by replacing each edge of \(G\) with a unit resistor. The Kirchhoff index \(Kf(G)\) is the sum of resistance distances between all pairs of vertices of the graph \(G\). In this paper, we determine the tricyclic graphs with the smallest and the second smallest Kirchhoff indices.

The basis number of a graph \(G\) is defined to be the least non-negative integer \(d\) such that there is a basis \(\mathcal{B}\) of the cycle space of \(G\) such that each edge of \(G\) is contained in at most \(d\) members of \(\mathcal{B}\). In this paper, we determine the basis number of the wreath product of different ladders.

The \(Co-PI\) index have been introduced by Hasani et al. recently. In this paper, we present a new version for the \(Co-PI\) index, and the Cartesian product, Corona product and join of graphs under this new index are computed.