Advanced Search

The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph $G$ with vertex set $V=\{v_1,v_2,\cdots ,v_n\}$, the extended double cover of $G$, denoted $G^{*}$, is the bipartite graph with bipartition $(X,Y)$ where $X=\{x_1,x_2,\cdots ,x_n\}$ and $Y=\{y_1,y_2,\cdots ,y_n\}$, 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...

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\left(u\right)+f\left(v\right)=f\left(w\right)$ for some vertex $w$ in $G$. 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 if it is adjacent to every other vertex...

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\left(O_1\right)-f\left(O_2\right)|\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\left(O_1\right)=p$ and $f\left(O_2\right)=q$, where $p<q$, then for any integer $k$ such that $p<k<q$, there are...

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...

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...