For any \( k \in \mathds{N} \), a graph \( G = (V, E) \) is said to be \( \mathds{Z}_k \)-magic if there exists a labeling \( l: E(G) \to \mathds{Z}_k – \{0\} \) such that the induced vertex set labeling \( l^+: V(G) \to \mathds{Z}_k \), defined by

$$ l^+(v) = \sum_{uv \in E(G)} l(uv) $$

is a constant map. For a given graph \( G \), the set of all \( k \in \mathds{N} \) for which \( G \) is \( \mathds{Z}_k \)-magic is called the integer-magic spectrum of \( G \) and is denoted by \( IM(G) \). In this paper, we will consider the functional extensions of \( P_n \) (\( n = 2, 3, 4 \)) and will determine their integer-magic spectra.

Let \( G(V, E) \) be a weighted connected simple graph. Given a pair of vertices \( u, v \in V \), let \( Max(u, v) \) denote the maximum average path value over all simple paths from \( u \) to \( v \). For a given simple path from \( u \) to \( v \), the average path value, \( apv_P(u, v) = \frac{min(P)}{length(P)} \), where \( min(P) \) is the weight of the minimum weight edge in the path \( P \) and \( length(P) \) is the number of edges in \( P \). This notion of average path value has been used in the analysis of social networks. Algorithms are presented for the calculation of \emph{average path value}.

For the purpose of large scale computing, we are interested in linking computers into large interconnection networks. In order for these networks to be useful, the underlying graph must possess desirable properties such as a large number of vertices, high connectivity, and small diameter. In this paper, we are interested in the alternating group graph, as an interconnection network, and the \( k \)-Disjoint Path Problem. In 2005, Cheng, Kikas, and Kruk showed that the alternating group graph, \( AG_n \), has the \( (n – 2) \)-Disjoint Path Property. However, their proof was an existence proof only; they did not show how to actually construct the \( (n – 2) \) disjoint paths. In 2006, Boats, Kikas, and Oleksik developed an algorithm for constructing three disjoint paths in the graph \( AG_5 \). Their algorithm exploited the hierarchical structure of \( AG_n \) to construct the paths. In this paper, we develop a purely algebraic algorithm that constructs the \( (n – 2) \) disjoint paths from scratch. This algebraic approach can be used for other Cayley graphs such as the split-star and the star graphs. Indeed, we believe that our approach can be used for any Cayley graph. We close with remarks on possible research directions stemming from this work.

The computation of the maximum toughness among graphs with \( n \) vertices and \( m \) edges is considered for \( \lceil{5n}/{2}\rceil \leq m < 3n \). We show that there are only finitely many cases in which the toughness value \( \frac{5}{2} \) cannot be achieved. This is in stark contrast with the known result that there is a \( \frac{3}{2} \)-tough graph on \( n \) vertices and \( \lceil{3n}/{2}\rceil \) edges if and only if \( n \equiv 0, 5 \pmod{6} \). However, constructions related to those used in the cubic case are also employed here. Our constructions additionally provide an infinite family of graphs that are supertough and not \( K_{1,3} \)-free.

A simple graphoidal cover of a graph \( G \) is a collection \( \psi \) of (not necessarily open) paths in \( G \) such that every path in \( \psi \) has at least two vertices, every vertex of \( G \) is an internal vertex of at most one path in \( \psi \), every edge of \( G \) is in exactly one path in \( \psi \), and any two paths in \( \psi \) have at most one vertex in common. The minimum cardinality of a simple graphoidal cover of \( G \) is called the simple graphoidal covering number of \( G \) and is denoted by \( \eta_s(G) \). In this paper, we determine the value of \( \eta_s \) for several families of graphs. We also obtain several bounds for \( \eta_s \) and characterize graphs attaining the bounds.

In this paper, we discuss how the addition of a new edge affects the irregularity strength of a graph.

Let \( G \) be a graph of size \( n \) with vertex set \( V(G) \) and edge set \( E(G) \). A \( \sigma \)-labeling of \( G \) is a one-to-one function \( f: V(G) \to \{0, 1, \dots, 2n\} \) such that \( \{|f(u) – f(v)| : \{u, v\} \in E(G)\} = \{1, 2, \dots, n\} \). Such a labeling of \( G \) yields cyclic \( G \)-decompositions of \( K_{2n+1} \) and of \( K_{2n+2} – F \), where \( F \) is a \( 1 \)-factor of \( K_{2n+2} \). It is conjectured that a \( 2 \)-regular graph of size \( n \) has a \( \sigma \)-labeling if and only if \( n \equiv 0 \) or \( 3 \pmod{4} \). We show that this conjecture holds when the graph has at most three components.

The Kneser graph \( K(m, n) \) (when \( m > 2n \)) has the \( n \)-subsets of an \( m \)-set as its vertices, two vertices being adjacent in \( K(m, n) \) whenever they are disjoint sets. The \( k \)th-chromatic number of any graph \( G \) (denoted by \( \chi_k(G) \)) is the least integer \( t \) such that the vertices can be assigned \( k \)-subsets of \( \{1, 2, \dots, t\} \) with adjacent vertices receiving disjoint \( k \)-sets. S. Stahl has conjectured that, if \( k = qn – r \) where \( q \geq 1 \) and \( 0 \leq r < n \), then \( \chi_k(K(m, n)) = qm – 2r \). This expression is easily verified when \( r = 0 \); Stahl has also established its validity for \( q = 1 \), for \( m = 2n + 1 \) and for \( k = 2, 3 \). We show here that the expression is also valid for all \( q \geq 2 \) in the following further classes of cases: \begin{enumerate}[label=(\roman*)] \item \( 2n + 1 < m \leq n(2 + r^{-1}) \) (\( 0 < r 1 \));
\item \( 4 \leq n \leq 6 \) and \( 1 \leq r \leq 2 \) (all \( m \));
\item \( 7 \leq n \leq 11 \) and \( r = 1 \) (all \( m \));
\item \( (n, r, m) = (7, 2, 18), (12, 1, 37), (12, 1, 38) \) or \( (13, 1, 40) \).
\end{enumerate}