On degree sets and the minimum orders in bipartite graphs
Y. Manoussakis ; H.P. Patil
Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 383-390 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

For any simple graph G, let D(G) denote the degree set {degG(v) : v ∈ V (G)}. Let S be a finite, nonempty set of positive integers. In this paper, we first determine the families of graphs G which are unicyclic, bipartite satisfying D(G) = S, and further obtain the graphs of minimum orders in such families. More general, for a given pair (S, T) of finite, nonempty sets of positive integers of the same cardinality, it is shown that there exists a bipartite graph B(X, Y ) such that D(X) = S, D(Y ) = T and the minimum orders of different types are obtained for such graphs

Publié le : 2014-01-01
EUDML-ID : urn:eudml:doc:268007 
@article{bwmeta1.element.doi-10_7151_dmgt_1742,
     author = {Y. Manoussakis and H.P. Patil},
     title = {On degree sets and the minimum orders in bipartite graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {34},
     year = {2014},
     pages = {383-390},
     zbl = {1290.05063},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1742}
}

Y. Manoussakis; H.P. Patil. On degree sets and the minimum orders in bipartite graphs. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 383-390. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1742/

[1] F. Harary, Graph Theory (Addison-Wesley, Reading Mass, 1969).

[2] S.F. Kapoor, A.D. Polimeni and C.W. Wall, Degree sets for graphs, Fund. Math. XCV (1977) 189-194. | Zbl 0351.05129

[3] Y. Manoussakis, H.P. Patil and V. Sankar, Further results on degree sets for graphs, AKCE Int. J. Graphs Comb. 1 (2004) 77-82. | Zbl 1065.05032

[4] Y. Manoussakis and H.P. Patil, Bipartite graphs and their degree sets, R.C. Bose Centenary Symposium on Discrete Mathematics and Applications, (Kolkata India, 15-21 Dec. 2002), Electron. Notes Discrete Math. 15 (2003) 125. doi:10.1016/S1571-0653(04)00554-2[Crossref]

[5] S. Pirzada, T.A. Naikoo, and F.A. Dar, Degree sets in bipartite and 3-partite graphs, Orient. J. Math Sciences 1 (2007) 39-45. | Zbl 1144.05308

[6] A. Tripathi and S. Vijay, On the least size of a graph with a given degree set, Discrete Appl. Math. 154 (2006) 2530-2536. doi:10.1016/j.dam.2006.04.003 [Crossref] | Zbl 1110.05024