Let $G$ be a simple graph. A function $f$ from the set of orientations of $G$ to the set of non-negative integers is called a continuous function on orientations of $G$ if, for any two orientations $O_1$ and $O_2$ of $G$, $|f(O_1)-f(O_2)|\le 1$ whenever $O_1$ and $O_2$ differ in the orientation of exactly one edge of $G$. We show that any continuous function on orientations of a simple graph $G$ has the interpolation property as follows: If there are two orientations $O_1$ and $O_2$ of $G$ with $f(O_1)=p$ and $f(O_2)=q$, where $p<q$, then for any integer $k$ such that $p<k<q$, there are at least $m$ orientations $O$ of $G$ satisfying $f(O) = k$, where $m$ equals the number of edges of $G$. It follows that some useful invariants of digraphs including the connectivity, the arc-connectivity and the absorption number, etc., have the above interpolation property on the set of all orientations of $G$.
The study on limit points of eigenvalues of undirected graphs was initiated by A. J. Hoffman in 1972. Now we extend the study to digraphs. We prove: 1. Every real number is a limit point of eigenvalues of graphs. Every complex number is a limit point of eigenvalues of digraphs. 2. For a digraph $D$, the set of limit points of eigenvalues of iterated subdivision digraphs of $D$ is the unit circle in the complex plane if and only if $D$ has a directed cycle. 3. Every limit point of eigenvalues of a set $\mathcal {D}$ of digraphs (graphs) is a limit point of eigenvalues of a set $\ddot{\mathcal {D}}$ of bipartite digraphs (graphs), where $\ddot{\mathcal {D}}$ consists of the double covers of the members in $\mathcal {D}$. 4. Every limit point of eigenvalues of a set $\mathcal {D}$ of digraphs is a limit point of eigenvalues of line digraphs of the digraphs in $\mathcal {D}$. 5. If $M$ is a limit point of the largest eigenvalues of graphs, then $-M$ is a limit point of the smallest eigenvalues of graphs.
Let $G$ be a connected simple graph on $n$ vertices. The Laplacian index of $G$, namely, the greatest Laplacian eigenvalue of $G$, is well known to be bounded above by $n$. In this paper, we give structural characterizations for graphs $G$ with the largest Laplacian index $n$. Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on $n$ and $k$ for the existence of a $k$-regular graph $G$ of order $n$ with the largest Laplacian index $n$. We prove that for a graph $G$ of order $n \geq 3$ with the largest Laplacian index $n$, $G$ is Hamiltonian if $G$ is regular or its maximum vertex degree is $\triangle (G)=n/2$. Moreover, we obtain some useful inequalities concerning the Laplacian index and the algebraic connectivity which produce miscellaneous related results.
As introduced by F. Harary in 1994, a graph $ G$ is said to be an $integral$ $ sum$ $ graph$ if its vertices can be given a labeling $f$ with distinct integers so that for any two distinct vertices $u$ and $v$ of $G$, $uv$ is an edge of $G$ if and only if $ f(u)+f(v)=f(w)$ for some vertex $w$ in $G$. \endgraf We prove that every integral sum graph with a saturated vertex, except the complete graph $K_3$, has edge-chromatic number equal to its maximum degree. (A vertex of a graph $G$ is said to be {\it saturated} if it is adjacent to every other vertex of $G$.) Some direct corollaries are also presented.
The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph $G$ with vertex set $V = \lbrace v_1,v_2, \dots , v_n \rbrace $, the extended double cover of $G$, denoted $G^*$, is the bipartite graph with bipartition $(X,Y)$ where $X = \lbrace x_1, x_2, \dots ,x_n \rbrace $ and $ Y = \lbrace y_1, y_2, \cdots ,y_n \rbrace $, in which $x_i$ and $y_j$ are adjacent iff $i=j$ or $v_i$ and $v_j$ are adjacent in $G$. In this paper we obtain formulas for the characteristic polynomial and the spectrum of $G^*$ in terms of the corresponding information of $G$. Three formulas are derived for the number of spanning trees in $G^*$ for a connected regular graph $G$. We show that while the extended double covers of cospectral graphs are cospectral, the converse does not hold. Some results on the spectra of the $n$th iterared double cover are also presented.