In this paper, we define, for a graph invariant \(\psi\), the deck ratio of \(\psi\) by \(D_\psi(G) = \frac{\psi(G)}{\Sigma_{v\in V(G)}\psi(G-v)}\). We give generic upper and lower bounds on \(D_\psi\) for monotone increasing and monotone decreasing invariants \(\psi\), respectively.

Then, we proceed to consider the Wiener index \(W(G)\), showing that \(D_W(G) \leq \frac{1}{|V(G)|-2}\). We show that equality is attained for a graph \(G\) if and only if every induced \(P_3\) subgraph of \(G\) is contained in a \(C_4\) subgraph. Such graphs have been previously studied under the name of self-repairing graphs.

We show that a graph on \(n \geq 4\) vertices with at least \(\frac{n^2-3n+6}{2} – n + 3\) edges is necessarily a self-repairing graph and that this is the best possible result. We also show that a \(2\)-connected graph is self-repairing if and only if all factors in its Cartesian product decomposition are.

Finally, some open problems about the deck ratio and about self-repairing graphs are posed at the end of the paper.

For a graph \(X\) and a digraph \(D\), we define the \(\beta\) transformation of \(X\) and the \(\alpha\) transformation of \(D\) denoted by \(X^\beta\) and \(D^\alpha\), respectively.\(D^\alpha\) is defined as the bipartite graph with vertex set \(V(D) \times \{0,1\}\) and edge set \(\{((v_i,0), (v_j, 1)) \mid v_i v_j \in A(D)\}\).\(X^\beta\) is defined as the bipartite graph with vertex set \(V(X) \times \{0,1\}\) and edge set \(\{((v_i,0), (v_j, 1)) \mid v_i v_j \in A(X)\}\), where \(X\) is the associated digraph of \(X\).In this paper, we give the relation between the eigenvalues of the digraph \(D\) and the graph \(D^\alpha\) when the adjacency matrix of \(D\) is normal. Especially, we obtain the eigenvalues of \(D^\alpha\) when \(D\) is some special Cayley digraph.

To study orthogonal arrays and signed orthogonal arrays, Ray-Chaudhuri and Singhi (\(1988\) and \(1994\)) considered some module spaces. Here, using a linear algebraic approach, we define an inclusion matrix and find its rank. In the special case of Latin squares, we show that there is a straightforward algorithm for generating a basis for this matrix using the so-called intercalates. We also extend this last idea.

Integral circulant graphs have been proposed as potential candidates for modelling quantum spin networks with perfect state transfer between antipodal sites in the network. We show that the diameter of these graphs is at most \(O(\ln \ln n)\), and further improve the recent result of Saxena, Severini, and Shparlinski.

We present a bijective proof of the hook length formula for rooted trees based on the ideas of the bijective proof of the hook length formula for standard tableaux by Novelli, Pak, and Stoyanovskii \([10]\). In Section \(4\), we present another bijection for the formula.

In this paper, we give sufficient conditions for the existence of kernels by monochromatic directed paths (m.d.p.) in digraphs with quasi-transitive colorings. Let \(D\) be an \(m\)-colored digraph. We prove that if every chromatic class of \(D\) is quasi-transitive, every cycle is quasi-transitive in the rim and \(D\) does not contain polychromatic triangles, then \(D\) has a kernel by m.d.p. The same result is valid if we preserve the first two conditions before and replace the last one by: there exists \(k \geq 4\) such that every \(\overrightarrow{C}_k\) is quasi-monochromatic and every \(\overrightarrow{C}_{k-1}\) (\(3 \leq l \leq k-1\)) is not polychromatic. Finally, we also show that if every chromatic class of \(D\) is quasi-transitive, every cycle in \(D\) induces a quasi-transitive digraph and \(D\) does not contain polychromatic \(\overrightarrow{C}_3\), then \(D\) has a kernel by m.d.p. Some corollaries are obtained for the existence of kernels by m.d.p. in \(m\)-colored tournaments.

The determination of the zero-capacity of a noisy channel has inspired research on the independence number of the strong product of odd cycles. The independence number for two infinite families of the strong product of three odd cycles is considered in this paper. In particular, we present the independence number of \(C_7 \boxtimes C_9 \boxtimes C_{2k+1}\) and an upper bound on the independence number of \(C_{13} \boxtimes C_3 \boxtimes C_{2k+1}\). The results are partially obtained by a computer search.

The strong product \(G_1 \boxtimes G_2\) of graphs \(G_1\) and \(G_2\) is the graph with \(V(G_1) \times V(G_2)\) as the vertex set, and two distinct vertices \((x_1,x_2)\) and \((y_1,y_2)\) are adjacent whenever for each \(i \in \{1,2\}\) either \(x_i = y_i\) or \(x_iy_i \in E(G_i)\).

An edge irregular total \(k\)-labeling \(\varphi: V \cup E \to \{1,2,\ldots,k\}\) of a graph \(G = (V, E)\) is a labeling of vertices and edges of \(G\) in such a way that for any different edges \(xy\) and \(x’y’\) their weights \(\varphi(x) + \varphi(xy) + \varphi(y)\) and \(\varphi(x’) + \varphi(x’y’) + \varphi(y’)\) are distinct. The total edge irregularity strength, \(\text{tes}(G)\), is defined as the minimum \(k\) for which \(G\) has an edge irregular total \(k\)-labeling.

We have determined the exact value of the total edge irregularity strength of the strong product of two paths \(P_n\) and \(P_m\).

Given \(m, n\) and \(2 \leq l \leq mn\), we study the problem of separating \(l\) symbols on an \(m \times n\) array such that the minimum \(\ell_1\) distance between any two of the \(l\) symbols is as large as possible. This problem is similar in nature to the well-known Tammes’ problem where one tries to achieve the largest angular separation for a given number of points on a \(2-D\) or higher dimensional sphere. It is also closely related to the well-studied problem of constructing optimal interleaving schemes for correcting error bursts in multi-dimensional digital data where a burst can be an arbitrarily shaped connected region in the array. Moreover, the interest in studying this problem also arises from considerations of minimizing the risk of multiple nearby node failures in a distributed data storage system (or a similar industrial network) in the event of a relatively large scale random disruption. We derive bounds on the maximum possible distance of separation for general \(m,n\) and \(l\), and provide also optimal constructions in several special cases including small and large \(l\) values, small \(m\) (or \(n\)) values, and \(n-1 \geq (l-1)(m-1)\).

In this paper, we apply the concepts of intuitionistic fuzzy sets to coalgebras. We give the definition of intuitionistic fuzzy subcoalgebras and investigate some properties of intuitionistic fuzzy subcoalgebras. Considering the applications of intuitionistic fuzzy subcoalgebras, we discuss their properties under homomorphisms of coalgebras.