On degree sets and the minimum orders in bipartite graphs

• Autorzy: Y. Manoussakis , H.P. Patil
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

degree sets; unicyclic graphs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 2
• Strony: 383-390

Daty

wydano

2014-05-01

online

2014-04-12

Twórcy

autor

Y. Manoussakis

• Université Paris XI (Orsay) L.R.I., Bât. 490, F-91405 Orsay Cédex, France

autor

H.P. Patil

• Department of Mathematics Pondicherry University Puducherry, India

Bibliografia

• [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.
• [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.
• [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.
• [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]

Identyfikatory

DOI

10.7151/dmgt.1742