On degree sets in k-partite graphs

T. A. Naikoo; U. Samee; S. Pirzada; Bilal A. Rather

doi:10.2478/ausi-2020-0015

Abstract

The degree set of a k-partite graph is the set of distinct degrees of its vertices. We prove that every set of non-negative integers is a degree set of some k-partite graph.

References

[1] T. S. Ahuja, A. Tripathi, On the order of a graph with a given degree set. J. Comb. Math. Comb. Comput., 57 (2006) 157–162. ⇒252
Search in Google Scholar Back to article
[2] G. Chartrand, R. J. Gould, S. F. Kapoor, Graphs with prescribed degree sets and girth, Periodica Math. Hung., 12, 4 (1981) 261–266. ⇒25210.1007/BF01849614
Search in Google Scholar Back to article
[3] A. A. Chernyak, Minimal graphs with a given degree set and girth (Russian), Vestsi Akad. Navuk BSSR Ser. Fiz.-Mat. Navuk,1988, 2 21–25, 123. ⇒252
Search in Google Scholar Back to article
[4] F. Harary, E. Harzheim, The degree sets of connected infinite graphs. Fund. Math., 118, 3 (1983) 233–236. ⇒25210.4064/fm-118-3-233-236
Search in Google Scholar Back to article
[5] A. Iványi, J. Elek, Degree sets of tournaments, Studia Univ. Babe¸s-Bolyai, Informatica, 59 (2014) 150–164. ⇒252
Search in Google Scholar Back to article
[6] F. Harary, Graph Theory, Reading, MA, Addison-Wesley (1969). ⇒25110.21236/AD0705364
Search in Google Scholar Back to article
[7] A. Iványi, S. Pirzada and F. A. Dar, Tripartite graphs with given degree set, Acta Univ. Sap. Informatica, 7, 1 (2015) 72–106. ⇒25210.1515/ausi-2015-0013
Search in Google Scholar Back to article
[8] S. F. Kapoor, A. D. Polimeni, C. E. Wall, Degree sets for graphs, Fund. Math., 95, 3 (1977) 189–194. ⇒25110.4064/fm-95-3-189-194
Search in Google Scholar Back to article
[9] S. Koukichi and H. Katsuhiro, Some remarks on degree sets for graphs, Rep. Fac. Sci. Kogoshima Univ., 32 (1999) 9–14. ⇒252
Search in Google Scholar Back to article
[10] Y. Manoussakis, H. P. Patil, V. Shankar, Further results on degree sets for graphs, AKCE J. Graphs Combin., 1, 2 (2004) 77–82. ⇒252
Search in Google Scholar Back to article
[11] Y. Manoussakis, H. P. Patil, Bipartite graphs and their degree sets, Electron. Notes on Discrete Math., (Proceedings of the R. C. Bose Centenary Symposium on Discrete Mathematics and Applications,) 15 (2003) 125–125. ⇒25210.1016/S1571-0653(04)00554-2
Search in Google Scholar Back to article
[12] Y. Manoussakis, H. P. Patil, On degree sets and the minimum orders in bipartite graphs, Discussiones Math. Graph Theory,34, 2 (2014) 383–390. ⇒25210.7151/dmgt.1742
Search in Google Scholar Back to article
[13] C. M. Mynhardt, Degree sets of degree uniform graphs, Graphs Comb., 1 (1985) 183–190. ⇒25210.1007/BF02582953
Search in Google Scholar Back to article
[14] S. Osawa, Y. Sabata, Degree sequences related to degree sets, Kokyuroki, 1744 (2011) 151–158. ⇒252
Search in Google Scholar Back to article
[15] S. Pirzada and Y. Jian Hua, Degree sequences in graphs, J. Math. Study,39,1 (2006) 25–31. ⇒252
Search in Google Scholar Back to article
[16] S. Pirzada, T. A. Naikoo and F. A. Dar, Degree sets in bipartite and 3-partite graphs, Oriental J. Math. Sci., 1,1 (2007) 39–45. ⇒252
Search in Google Scholar Back to article
[17] S. Pirzada, F. A. Dar, Signed degree sets in signed tripartite graphs, Matematicki Vesnik, 59 (3) (2007) 121–124. ⇒25210.1007/s10587-007-0079-z
Search in Google Scholar Back to article
[18] S. Pirzada, F. A. Dar, Signed degree sequences in signed tripartite graphs, J. Korean Soc. Ind, Appl. Math., 11, 2 (2007) 9–14. ⇒252
Search in Google Scholar Back to article
[19] S. Pirzada, Merajuddin, T. A. Naikoo, Score sets in oriented 3-partite graphs, Analysis Theory Appl., 4 (2007) 363–374. ⇒25210.1007/s10496-007-0363-7
Search in Google Scholar Back to article
[20] S. Pirzada, T. A. Naikoo, Score sets in oriented k-partite graphs, AKCE J. Graphs Combin., 3, 2 (2006) 135–145. ⇒252
Search in Google Scholar Back to article
[21] S. Pirzada, T. A. Naikoo, Score sets in k-partite tournaments, J. Appl. Math. Comp., 22, 1–2 (2006) 237–245. ⇒25210.1007/BF02896474
Search in Google Scholar Back to article
[22] S. Pirzada, T. A. Naikoo, Score sets in oriented graphs, Appl. Anal. Discrete Math., 2 1 (2008) 107–113. ⇒25210.2298/AADM0801107P
Search in Google Scholar Back to article
[23] S. Pirzada, T. A. Naikoo, T. A. Chishti, Score sets in oriented bipartite graphs, Novi Sad J. Math, 36, 1 (2006) 35–45. ⇒252
Search in Google Scholar Back to article
[24] S. Pirzada, T. A. Naikoo, F. A. Dar, Signed degree sets in signed graphs, Czechoslovak Math. J., 57, 3 (2007) 843–848. ⇒25210.1007/s10587-007-0079-z
Search in Google Scholar Back to article
[25] S. Pirzada, An Introduction to Graph Theory, Universities Press, Hyderabad, India, 2012. ⇒251
Search in Google Scholar Back to article
[26] S. Pirzada, T. A. Naikoo, F. A. Dar, A note on signed degree sets in signed bipartite graphs, Appl. Anal. Discrete Math., 2, 1 (2008) 114–117. ⇒25210.2298/AADM0801114P
Search in Google Scholar Back to article
[27] K. B. Reid. Score sets for tournaments, Congressus Numer., 21 (1978) 607–618. ⇒252
Search in Google Scholar Back to article
[28] T. A. Sipka, The orders of graphs with prescribed degree sets, J. Graph Theory, 4, 3 (1980) 301–307. ⇒10.1002/jgt.3190040308
Search in Google Scholar Back to article
[29] A. Tripathi, S. Vijay, On the least size of a graph with a given degree set, Discrete Appl. Math., 154 (2006) 2530–2536. ⇒25210.1016/j.dam.2006.04.003
Search in Google Scholar Back to article
[30] A. Tripathi, S. Vijay, A short proof of a theorem on degree sets of graphs, Discrete Appl. Math., 155 (2007) 670–671. ⇒25210.1016/j.dam.2006.09.006
Search in Google Scholar Back to article
[31] L. Volkmann, Some remarks on degree sets of multigraphs, J. Combin. Math. Combin. Comput., 77 (2011) 45–49. ⇒252
Search in Google Scholar Back to article

On degree sets in k-partite graphs

Abstract

Paradigm

My account