In this paper, we study the relations between degree sum and extending paths in graphs. The following result is proved. Let \(G\) be a graph of order \(n\), if \(d(u)+d(v) \geq n+k\) for each pair of nonadjacent vertices \(u,v\) in \(V(G)\), then every path \(P\) of \(G\) with \(\frac{n}{k+2} \leq 2 < n\) is extendable. The bound \(\frac{n}{k+2}+2\) is sharp.

A median graph is a connected graph in which, for every three vertices, there exists a unique vertex \(m\) lying on the geodesic between any two of the given vertices. We show that the only median graphs of the direct product \(G \times H\) are formed when \(G = P_k\), for any integer \(k \geq 3\), and \(H = P_l\), for any integer \(l \geq 2\), with a loop at an end vertex, where the direct product is taken over all connected graphs \(G\) on at least three vertices or at least two vertices with at least one loop, and connected graphs \(H\) with at least one loop.

An urn contains \(m\) distinguishable balls with \(m\) distinguishable colors. Balls are drawn for \(n\) times successively at random
and with replacement from the urn. The mathematical expectation of the number of drawn colors is investigated. Some combinatorial identities on the Stirling number of the second kind \(S(n,m)\) are derived by using probabilistic method.

Let \(G\) be a finite group. The commutativity degree of \(G\), written \(d(G)\), is defined as the ratio \[\frac{|\{(x, y)x,y \in G, xy = yx\}|}{|G|^2}\]. In this paper, we examine the commutativity degree of groups of nilpotency class 2 and, by using numerical solutions of the equation \(xy \equiv zu \pmod{n}\), we give certain explicit formulas for some particular classes of finite groups. A lower bound for \(d(G)\) is obtained for \(2\)-generated groups of nilpotency class \(2\).

For a graph \(G\), the Hosoya index is defined as the total number of its matchings. A generalized \(\theta\)-graph \((r_1, r_2, \ldots, r_k)\) consists of a pair of end vertices joined by \(k\) internally disjoint paths of lengths \(r_1 + 1, r_2 + 1, \ldots, r_k + 1\). Let \(\Theta_k\) denote the set of generalized \(\theta\)-graphs with \(k \geq 4\). In this paper, we obtain the smallest and the largest Hosoya index of the generalized \(\theta\)-graph in \(\Theta_n^k\), respectively. At the same time, we characterize the corresponding extremal graphs.

The purpose of this paper is to solve the odd minimum \(S\)-cut, the odd minimum \(\bar{T}\)-cut, and the odd minimum \((S, T)\)-cut problems in directed graphs using triple families. We also provide here two properties of triple families.

Let \(G\) be a graph and let \(\delta(G)\) denote the minimum degree of \(G\). Let \(F\) be a given connected graph. Suppose that \(|V(G)|\) is a multiple of \(|V(F)|\). A spanning subgraph of \(G\) is called an \(F\)-factor if its components are all isomorphic to \(F\). In 2002, Kawarabayashi [5] conjectured that if \(G\) is a graph of order \(n\) (\(n \geq 3\)) with \(\delta(G) \geq \frac{\ell^2-3\ell+1}{\ell-2}\), then \(G\) has a \(K_\ell^-\)-factor, where \(K_\ell^-\) is the graph obtained from \(K_\ell\) by deleting just one edge. In this paper, we prove that this conjecture is true when \(\ell = 5\).

The \(b\)-chromatic number \(b(G)\) of a graph \(G\) is defined as the maximum number \(k\) of colors in a proper coloring of the vertices of \(G\) in such a way that each color class contains at least one vertex adjacent to a vertex of every other color class. Let \(\mu(G)\) denote the Mycielskian of \(G\). In this paper, it is shown that if \(G\) is a graph with \(b\)-chromatic number \(b\) and for which the number of vertices of degree at least \(b\) is at most \(2b – 2\), then \( b(\mu(G))\) lies in the interval \([b+1, 2b-1]\). As a consequence, it follows that \(b(G)+1 \leq b(\mu(G)) \leq 2b(G) -1\) for \(G\) in any of the following families: split graphs, \(K_{n,n} – \{a \ 1\text{-factor}\}\), the hypercubes \(Q_p\), where \(p \geq 3\), trees, and a special class of bipartite graphs. We show further that for any positive integer \(b\) and every integer \(k \in [b+1, 2b-1]\), there exists a graph \(G\) belonging to the family mentioned above, with \(b(G) = b\) and \(b(\mu(G)) = k\).

For a graph \(G = (V,E)\), the Schultz index of \(G\) is defined as \(S(G) = \sum\limits_{\{u,v \}\subseteq V(G)} (d_G(u) + d_G(v))d_G(u,v)\), where \(d_G(u)\) is the degree of the vertex \(u\) in \(G\), and \(d_G(u,v)\) is the distance between \(u\) and \(v\) in \(G\). In this paper, we investigate the Schultz index of tricyclic graphs. The \(n\)-tricyclic graphs with the minimum Schultz index are determined.

In this paper, we investigate the existence of perfect state transfer in integral circulant graphs between non-antipodal vertices—vertices that are not at the diameter of a graph. Perfect state transfer is considered on circulant quantum spin networks with nearest-neighbor couplings. The network is described by a circulant graph \(G\), which is characterized by its circulant adjacency matrix \(A\). Formally, we say that there exists perfect state transfer (PST) between vertices \(a, b \in V(G)\) if \(|F(\tau)_{ab}| = 1\) for some positive real number \(\tau\), where \(F(\tau) = \exp(itA)\). Saxena, Severini, and Shparlinski (International Journal of Quantum Information 5 (2007), 417-430) proved that \(|F(\tau)_{aa}| = 1\) for some \(a \in V(G)\) and \(t \in \mathbb{R}\) if and only if all the eigenvalues of \(G\) are integers (that is, the graph is integral). The integral circulant graph \(ICG_n(D)\) has the vertex set \(\mathbb{Z}_n = \{0, 1, 2, \ldots, n-1\}\) and vertices \(a\) and \(b\) are adjacent if \(\gcd(a-b, n) \in D\), where \(D \subseteq \{d: d|n, 1 \leq d \leq n\}\). We characterize completely the class of integral circulant graphs having PST between non-antipodal vertices for \(|D| = 2\). We have thus answered the question posed by Godsil on the existence of classes of graphs with PST between non-antipodal vertices. Moreover, for all values of \(n\) such that \(ICG_n(D)\) has PST (\(n \in 4\mathbb{N}\)), several classes of graphs \(ICG_n(D)\) are constructed such that PST exists between non-antipodal vertices.