Previous |  Up |  Next

# Article

Full entry | PDF   (0.3 MB)
Keywords:
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

Partner of