Advanced Search

The basis number of a graph $G$ is defined by Schmeichel to be the least integer $h$ such that $G$ has an $h$-fold basis for its cycle space. MacLane showed that a graph is planar if and only if its basis number is $\le 2$. Schmeichel proved that the basis number of the complete graph $K_n$ is at most $3$. We generalize the result of Schmeichel by showing that the basis number of the $d$-th power of $K_n$ is at most $2d+1$.

Let $G$ be an undirected simple connected graph, and $e=uv$ be an edge of $G$. Let $N_G\left(e\right)$ be the subgraph of $G$ induced by the set of all vertices of $G$ which are not incident to $e$ but are adjacent to $u$ or $v$. Let ${𝒩}_e$ be the class of all graphs $H$ such that, for some graph $G$, $N_G\left(e\right)\cong H$ for every edge $e$ of $G$. Zelinka [3] studied edge neighborhood graphs and obtained some special graphs in ${𝒩}_e$. Balasubramanian and Alsardary [1] obtained some other graphs in ${𝒩}_e$. In this paper we given some new graphs in ${𝒩}_e$.

The basis number of a graph $G$ was defined by Schmeichel to be the least integer $h$ such that $G$ has an $h$-fold basis for its cycle space. He proved that for $m,n\ge 5$, the basis number $b\left(K_{m,n}\right)$ of the complete bipartite graph $K_{m,n}$ is equal to 4 except for $K_{6,10}$, $K_{5,n}$ and $K_{6,n}$ with $n=5,6,7,8$. We determine the basis number of some particular non-planar graphs such as $K_{5,n}$ and $K_{6,n}$, $n=5,6,7,8$, and $r$-cages for $r=5,6,7,8$, and the Robertson graph.