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.

Chemical indices are introduced to correlate chemical compounds’ physical properties with their structures. Among recently introduced such indices, the eccentric connectivity index of a graph \(G\) is defined as \(\xi^C(G) = \sum_{v \in V(G)} deg(v) ec(v)\), where \(deg(v)\) is the degree of a vertex \(v\) and \( ec(v)\) is its eccentricity. The extremal values of \(\xi^C(G)\) have been studied among graphs with various given parameters. In this note, we study trees with extremal values of the eccentric connectivity index with a given degree sequence. The extremal structures are identified; however, they are not unique.

A \(k\)-L\((d, 1)\)-labeling of a graph \(G\) is a function \(f\) from the vertex set \(V(G)\) to \(\{0, 1, \ldots, k\}\) such that \(|f(u) – f(v)| > 1\) if \(d(u,v) = 2\) and \(|f(u) – f(v)| \geq d\) if \(d(u,v) = 1\). The L\((d,1)\)-labeling number \(\lambda(G)\) of \(G\) is the smallest number \(k\) such that \(G\) has a \(k\)-L\((d, 1)\)-labeling. In this paper, we show that \(2d+2 \leq \lambda(C_m \square C_n) \leq 2d+4\) if either \(m\) or \(n\) is odd. Furthermore, the following cases are determined: (a) \(\lambda_d(C_3 \square C_n)\) and \(\lambda_d(C_4 \square C_n)\) for \(d \geq 3\), (b) \(\lambda_d(C_m \square C_n)\) for some \(m\) and \(n\), (c) \(\lambda_d(C_{2m} \square C_{2n})\) for \(d \geq 5\) when \(m\) and \(n\) are even.

The purpose of this paper is to establish several identities involving \(q\)-harmonic numbers by the \(q\)-Chu-Vandermonde convolution formula and obtain some \(q\)-analogues of several known identities.

It will be proved that the problem of determining whether a set of vertices of a dually chordal graphs is the set of leaves of a tree compatible with it can be solved in polynomial time by establishing a connection with finding clique trees of chordal graphs with minimum number of leaves.

A vertex subset \(F\) is an \(R_k\)-vertex-cut of a connected graph \(G\) if \(G – F\) is disconnected and every vertex in \(G – F\) has at least \(k\) neighbors in \(G – F\). The cardinality of the minimum \(R_k\)-vertex-cut of \(G\) is the \(R_k\)-connectivity of \(G\), denoted by \(\kappa^k(G)\). This parameter measures a kind of conditional fault tolerance of networks. In this paper, we determine \(R_2\)-connectivity and \(R_3\)-connectivity of recursive circulant graphs \(G(2^m, 2)\).