Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
graphs; basis number; cycle space; basis
graphs; basis number; cycle space; basis
Summary:
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.
References:
[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
Search
Partner of
