Previous |  Up |  Next


graphs; basis number; cycle space; basis
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(K_{m,n})$ 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.
[1] A. A.  Ali and S. Y.  Alsardary: On the basis number of a graph. Dirasat (Science) 14 (1987), 43–51.
[2] J. A.  Banks and E. F.  Schmeichel: The basis number of the $n$-cube. J.  Combin Theory, Ser.  B 33 (1982), 95–100. DOI 10.1016/0095-8956(82)90061-2 | MR 0685059
[3] J. A.  Bondy and S. R.  Murty: Graph Theory with Applications. Amer. Elsevier, New York, 1976. MR 0411988
[4] F.  Harary: Graph Theory. 2nd ed., Addison-Wesely, Reading, Massachusetts, 1971.
[5] S.  MacLane: A combinatorial condition for planar graphs. Fund. Math. 28 (1937), 22–32. Zbl 0015.37501
[6] N.  Robertson: The smallest graph of girth  5 and valency  4. Bull. Amer. Math. Soc. 30 (1981), 824–825. MR 0167974
[7] E. F.  Schmeichel: The basis number of a graph. J.  Combin. Theory, Ser.  B 30 (1981), 123–129. DOI 10.1016/0095-8956(81)90057-5 | MR 0615307 | Zbl 0385.05031
[8] W. T.  Tutte: Connectivity in Graphs. Univ. Toronto press, Toronto, 1966. MR 0210617 | Zbl 0146.45603
Partner of
EuDML logo