For general graphs \(G\), it is known \([6]\) that the minimal length of an addressing scheme, denoted by \(N(G)\), is less than or equal to \(|G| – 1\). In this paper, we prove that for almost all complete bipartite graphs \(K_{m,n}\), \(N(K_{m,n}) = |K_{m,n}| – 2\).

A vertex subversion strategy of a graph \(G\) is a set of vertices \(X \subseteq V(G)\) whose closed neighborhood is deleted from \(G\). The survival subgraph is denoted by \(G/X\). The vertex-neighbor-integrity of \(G\) is defined to be \(VNI(G) = \min\{|X| + r(G/X) : X \subseteq V(G)\},\) where \(r(G/X)\) is the order of a largest component in \(G/X\). This graph parameter was introduced by Cozzens and Wu to measure the vulnerability of spy networks. It was proved by Gambrell that the decision problem of computing the vertex-neighbor-integrity of a graph is NP-complete. In this paper, we evaluate the vertex-neighbor-integrity of the composition graph of two paths.

In this paper, we prove that a matroid with at least two elements is connected if and only if it can be obtained from a loop by a nonempty sequence of non-trivial single-element extensions and series extensions.

Let \(G\) and \(H\) be graphs with a common vertex set \(V\), such that \(G – i \cong H – i\)for all \(i \in V\). Let \(p_i\) be the permutation of \(V – i\) that maps \(G – i\) to \(H – i\), and let \(q_i\) denote the permutation obtained from \(p_i\) by mapping \(i\) to \(i\). It is shown that certain algebraic relations involving the edges of \(G\) and the permutations \(q_iq_j^{-1}\) and \(q_iq_k^{-1}\), where \(i, j, k \in V\) are distinct vertices, often force \(G\) and \(H\) to be isomorphic.

The factorization of matrix \(A\) with entries \(a_{i,j}\) determined by \(a_{i,j} = \alpha a_{i-1,j-1} + \beta a_{i,j-1}\) is derived as \(A = TP^T\). An interesting factorization of matrix \(B\) with entries \(b_{i,j} = \alpha b_{i-1,j} + \beta b_{i,j-1}\) is given by \(B = P[\alpha]TP^{T}[\beta]\). The beautiful factorization of matrix \(C\) whose entries satisfy \(c_{i,j} = \alpha c_{i-1,j} + \beta c_{i-1,j-1} + Ye_{i-1,j-1}\) is founded to be \(C = P[\alpha]DP^T[\beta]\), where \(T\) is a Toeplitz matrix, and \(P\) and \(P[\alpha]\) are Pascal matrices. The matrix product factorization to the problem is solved perfectly so far.

Dirac showed that a \(2\)-connected graph of order \(n\) with minimum degree \(\delta\) has circumference at least \(\min\{2\delta, n\}\). We prove that a \(2\)-connected, triangle-free graph \(G\) of order \(n\) with minimum degree \(\delta\) either has circumference at least \(\min\{4\delta – 4, n\}\), or every longest cycle in \(G\) is dominating. This result is best possible in the sense that there exist bipartite graphs with minimum degree \(\delta\) whose longest cycles have length \(4\delta – 4\), and are not dominating.

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. It is proved here that \(\lceil \frac{\omega(G)}{2}\rceil \leq vla(G) \leq \lceil \frac{\omega(G)+1}{2}\rceil\) for a claw-free connected graph \(G\) having \(\Delta(G) \leq 6\), where \(\omega(G)\) is the clique number of \(G\).

An \(f\)-coloring of a graph \(G\) is a coloring of edges of \(E(G)\) such that each color appears at each vertex \(v \in V(G)\) at most \(f(v)\) times. The minimum number of colors needed to \(f\)-color \(G\) is called the \(f\)-chromatic index of \(G\) and denoted by \(\chi’_f(G)\). Any simple graph \(G\) has the \(f\)-chromatic index equal to \(\Delta_f(G)\) or \(\Delta_f(G) + 1\), where \(\Delta_f(G) = \max_{v \in V}\{\lceil \frac{d(v)} {f(v)}\rceil\}\). If \(\chi’_f(G) = \Delta_f(G)\), then \(G\) is of \(C_f\) \(1\); otherwise \(G\) is of \(C_f\) \(2\). In this paper, two sufficient conditions for a regular graph to be of \(C_f\) \(1\) or \(C_f\) \(2\) are obtained and two necessary and sufficient conditions for a regular graph to be of \(C_f\) \(1\) are also presented.

Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\), and let \(A\) be an abelian group. A labeling \(f: V(G) \to A\) induces an edge labeling \(f^*: E(G) \to A\) defined by \(f^*(xy) = f(x) + f(y)\), for each edge \(xy \in E(G)\). For \(i \in A\), let \(v_f(i) = \text{card}\{v \in V(G): f(v) = i\}\) and \(e_f(i) = \text{card}\{e \in E(G): f^*(e) = i\}\). Let \(c(f) = \{|e_f(i) – e_f(j)|: (i,j) \in A \times A\}\). A labeling \(f\) of a graph \(G\) is said to be \(A-friendly\) if \(|v_f(i) – v_f(j)| \leq 1\) for all \((i,j) \in A \times A\). If \(c(f)\) is a \((0,1)\)-matrix for an \(A\)-friendly labeling \(f\), then \(f\) is said to be \(A\)-cordial. When \(A = \mathbb{Z}_2\), the \({friendly index set}\) of the graph \(G\), \(FI(G)\), is defined as \(\{|e_f(0) – e_f(1)|: \text{the vertex labeling } f \text{ is } \mathbb{Z}_2\text{-friendly}\}\). In this paper, we determine the friendly index set of cycles, complete graphs, and some bipartite graphs.