A compilation of relations between graph invariants
1985; Wiley; Volume: 15; Issue: 1 Linguagem: Inglês
10.1002/net.3230150108
ISSN1097-0037
AutoresRobert C. Brigham, Ronald D. Dutton,
Tópico(s)Data Visualization and Analytics
ResumoNetworksVolume 15, Issue 1 p. 73-107 Article A compilation of relations between graph invariants Robert C. Brigham, Robert C. Brigham Department of Mathematics and Department of Computer Science, University of Central Florida, Orlando, Florida 32816Search for more papers by this authorRonald D. Dutton, Ronald D. Dutton Department of Mathematics and Department of Computer Science, University of Central Florida, Orlando, Florida 32816Search for more papers by this author Robert C. Brigham, Robert C. Brigham Department of Mathematics and Department of Computer Science, University of Central Florida, Orlando, Florida 32816Search for more papers by this authorRonald D. Dutton, Ronald D. Dutton Department of Mathematics and Department of Computer Science, University of Central Florida, Orlando, Florida 32816Search for more papers by this author First published: Spring 1985 https://doi.org/10.1002/net.3230150108Citations: 20AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onEmailFacebookTwitterLinkedInRedditWechat References 1 B. Andrásfai, Über ein extremalproblem der graphentheorie. Acta Math. A cad. Sci. Hunger. 13 (1962) 443–455. 10.1007/BF02020809 Google Scholar 2 M. Ajtai, V. Chvátal, M. M. Newborn and E. Szemerédi, Crossing-free subgraphs. Technical Report SOCS-79-21, School of Computer Science, McGill University, Montreal, February 1981 (Annals Discrete Math, in press.) Google Scholar 3 B. Andrásfai, P. Erdös and V. T. Sós, On the connection between chromatic number, maximal clique and minimal degree of a graph. Discrete Math. 8 (1974), 205–218. 10.1016/0012-365X(74)90133-2 Google Scholar 4 V. B. Alekseev, and V. S. Gončakov, The thickness of an arbitrary complete graph. Mat. Sb. (N. S.) 101 (143) (1976) No. 2, 212–230. Google Scholar [English translation: Math USSR-Sb. 30 (1976) No. 2, 187–207.] 10.1070/SM1976v030n02ABEH002267 Web of Science®Google Scholar 5 A. T. Amin, and S. L. Hakimi, Upper bounds on the order of a clique of a graph. SIAM J. Appl. Math. 22 (1972), 569–573. 10.1137/0122052 Web of Science®Google Scholar 6 Y. Alavi, and J. Mitchem, The connectivity and line-connectivity of complementary graphs. Recent Trends in Graph Theory (Proc. Conf., New York, 1970), Lecture Notes in Mathematics, Vol. 186, Springer, Berlin (1971), pp. 1–3. 10.1007/BFb0059416 Google Scholar 7 B. Bollobás, Graphs of given diameter. Theory of Graphs (Proc. Colloq. Tiliany, 1966). Academic Press, New York (1968), pp. 29–36. Google Scholar 8 B. Bollobás, Graphs with given diameter and maximal valency and with a minimal number of edges. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969). Academic Press, London (1971), pp. 25–37. Google Scholar 9 B. Bollobás, External Graph Theory. Academic Press, New York (1978). Google Scholar 10 J. C. Bermond, and B. Bollabás, The diameter of graphs-a survey, Proc. 12th Southeastern Conf. on Combinatorics, Graph Theory, and Computing (Louisiana State University, Baton Rouge, 1981); Congressus Numerantium, Vol. 32. Utilitas Math, Winnipeg (1981), pp. 3–27. Google Scholar 11 J. M. Benedict, and P. Z. Chinn, On graphs having prescribed clique number, chromatic number, and maximum degree. Theory and Application of Graphs (Proc. Internat. Conf., Western Michigan University, Kalamazoo, Michigan 1976), Lecture Notes in Math, 642. Springer, Berlin (1978), pp. 132–140. Google Scholar 12 M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and Digraphs. Prindle, Weber & Schmidt, Boston (1979). Google Scholar 13 R. C. Brigham, and R. D. Dutton, Graphs which with their complements have certain clique covering numbers. Discrete Math 34 (1981) 1–7. 10.1016/0012-365X(81)90016-9 Web of Science®Google Scholar 14 R. C. Brigham, and R. D. Dutton, On clique covers and independence numbers of graphs. Discrete Math. 44 (1983) 139–144. 10.1016/0012-365X(83)90054-7 Web of Science®Google Scholar 15 R. C. Brigham, and R. D. Dutton, Upper bounds on the edge clique cover number of a graph. Discrete Math. (in press). Google Scholar 16 B. Bollobás, and S. E. Eldridge, Maximal matchings in graphs with given maximal and minimal degrees. Proc. 5th British Combinatorial Conf. (University Aberdeen, Aberdeen, 1975). Congressus Numerantium, No. XV. Utilitas Math., Winnipeg, Manitoba (1976), pp. 165–168. Google Scholar 17 L. W. Beineke, and F. Harary, Inequalities involving the genus of a graph and its thicknesses. Proc. Glasgow Math. Assoc. 7 (1965) 19–21. 10.1017/S2040618500035097 Google Scholar 18 O. V. Borodin, and A. V. Kostǒcka, On an upper bound of a graph's chromatic number, depending on the graph's degree and density. J. Combinatorial Theory (B) 23 (1977) 247–250. 10.1016/0095-8956(77)90037-5 Web of Science®Google Scholar 19 J. A. Bondy, and U. S. R. Murty, Extremal graphs of diameter two with prescribed minimum degree. Studio Sci. Math. Hungar. 7 (1972) 239–241. Google Scholar 20 J. A. Bondy, Extremal graphs with prescribed covering number. J. Combinatorial Theory (B) 24 (1978) 51–52. 10.1016/0095-8956(78)90076-X Web of Science®Google Scholar 21 J. A. Bondy, Large cycles in graphs. Discrete Math. 1 (1971) 121–132. 10.1016/0012-365X(71)90019-7 Google Scholar 22 F. Buckley, Self-centered graphs with a given radius. Proc. 10th Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Florida, 1979). Congressus Numerantium XXIII. Utilitas, Winnipeg (1979), pp. 211–215. Google Scholar 23 D. M. Cvetković, Chromatic number and the spectrum of a graph. Publ. Inst. Math (Beograd) (N. S.) 14 (28) (1972) 25–38. Google Scholar 24 P. A. Catlin, Another bound on the chromatic number of a graph. Discrete Math. 24 (1978) 1–6. 10.1016/0012-365X(78)90167-X Web of Science®Google Scholar 25 P. Z. Chinn, J. Chvátolová, A. K. Dewdney and N. E. Gibbs, The bandwidth problem for graphs and matrices-a survey. J Graph Theory 6 (1982) 223–254. 10.1002/jgt.3190060302 Web of Science®Google Scholar 26 D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs. Academic Press, New York (1980). Web of Science®Google Scholar 27 F. R. K. Chung, P. Erdös and R. L. Graham, On the product of the point and line covering numbers of a graph. Second International Conference on Combinatorial Mathematics (New York, 1978). Ann. N. Y. Acad. Sci., 319 (1979) 597–602. 10.1111/j.1749-6632.1979.tb32840.x Google Scholar 28 G. Chartrand, A graph theoretic approach to a communications problem. J. SIAM Appl. Math 14 (1966) 778–781. 10.1137/0114065 Web of Science®Google Scholar 29 V. Chvátal, New directions in Hamiltonian graph theory. New Directions in the Theory of Graphs (Proc. Third Ann Arbor Conf. on Graph Theory). University of Michigan, Ann Arbor (1971), pp. 65–95. Google Scholar 30 V. Chvátal, Some relations among invariants of graphs Czecho Math J. 21 (1971) 366–368. Web of Science®Google Scholar 31 V. Chvátal, Degrees and matchings. J. Combinatorial Theory (B) 20 (1976) 128–138. 10.1016/0095-8956(76)90004-6 Web of Science®Google Scholar 32 V. Chvátal, The smallest triangle-free 4-chromatic 4-regular graph. J Combinatorial Theory 9 (1970) 93–94. 10.1016/S0021-9800(70)80057-6 Google Scholar 33 G. Chartrand, and H. V. Kronk, The point arboricity of planar graphs. J. London Math. Soc. 44 (1969) 612–616. 10.1112/jlms/s1-44.1.612 Web of Science®Google Scholar 34 G. Chartrand, H. V. Kronk and C. E. Wall, The point arboricity of a graph. Isr. J. Math. 6 (1968) 169–175. 10.1007/BF02760181 Web of Science®Google Scholar 35 M. Capobianco, and J. C. Molluzzo, Examples and Counterexamples in Graph Theory, North Holland, New York (1978). Google Scholar 36 R. J. Cook, Point arboricity and girth. J. London Math. Soc. (2), 8 (1974) 322–324. 10.1112/jlms/s2-8.2.322 Web of Science®Google Scholar 37 R. J. Cook, Point partition numbers and girth. Proc. Ameri. Math. Soc. 49 (1975), 510–514. 10.2307/2040674 Web of Science®Google Scholar 38 R. J. Cook, Heawood's theorem and connectivity. Mathematicka 20 (1973) 201–207. 10.1112/S0025579300004770 Web of Science®Google Scholar 39 R. J. Cook, Chromatic number and girth. Periodica Math. Hungar. 6 (1975) 103–107. 10.1007/BF02018401 Google Scholar 40 R. J. Cook, Analogues of Heawood's theorem. Combinatorics (Proc. British Combinatorial Conf.). Univ. Coll. Wales, Aberystwyth (1973), pp. 27–33. Google Scholar 41 E. J. Cockayne, Domination of undirected graphs-a survey. Theory and Application of Graphs in America's Bicentennial Year ( Y. Alavi and D. R. Lick, Eds.). Springer-Verlag, New York (1976). Google Scholar 42 S. A. Choudum, K. R. Parthasarathy and G. Ravindra, Line-clique cover number of a graph. Prod. Ind. Nat. Sci. Acad. 41 (1975) 289–293. Google Scholar 43 D. M. Cvetković, Inequalities obtained on the basis of the spectrum of the graph. Stud. Sci. Math. Hungar. 8 (1973) 433–436. Google Scholar 44 R. A. Duke, On the genus and connectivity of Hamiltonian graphs. Discrete Math. 2 (1972), 199–206. 10.1016/0012-365X(72)90003-9 Google Scholar 45 A. K. Dewdney, The bandwidth of a graph-some recent results. Proc. 7th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State University, Baton Rouge, LA, 1976). Congressus Numerantium XVII. Utilitas (1976), pp. 273–278. Google Scholar 46 G. A. Dirac, Valency-variety and chromatic number of abstract graphs. Wissen-schaftliche Zeitschrift der Martin-Luther Universität Halle-Wittenberg 13 (1964) 59–63. Google Scholar 47 P. Erdös, On the number of complete subgraphs and circuits contained in graphs. Časopis Pro Pěstov́ani Matematiky 94 (1969) 290–296. Google Scholar 48 S. E. Eldridge, and B. Bollobás, Maximal matchings in graphs with given minimal and maximal degrees. Math. Proc. Cambridge Philosoph. Soc. 79 (1976) 221–234. 10.1017/S0305004100052233 Web of Science®Google Scholar 49 C. S. Edwards, and C. H. Elphick, Lower bounds for the clique and the chromatic numbers of a graph. Discrete Appl. Math. 5 (1983) 51–64. 10.1016/0166-218X(83)90015-X Web of Science®Google Scholar 50 P. Erdös, and T. Gallai, On the minimal number of vertices representing the edges of a graph. Akad. Mat. Intezenck Kozlemanyai 6 (1961) 181–202. Google Scholar 51 P. Erdös, A. W. Goodman and L. Posa, The representation of a graph by set intersections. Canad. J. Math. 18 (1966) 106–112. 10.4153/CJM-1966-014-3 Web of Science®Google Scholar 52 S. Fiorini, and R. J. Wilson, On the chromatic index of a graph II. Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973), London Math Soc. Lecture Note Ser., No. 13. Cambridge Univ. Press, London (1974), pp. 37–51. Google Scholar 53 F. Gliviak, Maximal graphs with given connectivity and edge-connectivity. Mat. Casopis (Slovenska Academia Vied) 25 (1975), 99–103. Google Scholar 54 J. R. Griggs, Lower bounds on the independence number in terms of the degress. Presented at 793rd Meeting of the American Mathematical Society, Bryn Mawr College, Bryn Mawr, Pennsylvania, March 16-17 (1982). Google Scholar 55 F. Harary, Graph Theory. Addison Wesley, Reading, MA (1969). 10.21236/AD0705364 Google Scholar 56 P. Hansen, Degres et nombre de stabilité d'un graphe. Colloque Sur La Theorie Des Graphes (Paris, 1974). Cahiers Centre Etudes Recherche Oper., V. 17 (1975). Google Scholar 57 P. Hansen, Upper bounds for the stability number of a graph. Rev. Roum. Math. Pures Appl. 24 (1979) 1195–1199. Google Scholar 58 B. Jackson, Hamiltonian cycles in regular graphs. J. Graph Theory 2 (1978) 363–365. 10.1002/jgt.3190020412 Google Scholar 59 H. V. Kronk, The chromatic number of triangle-free graphs, Graph Theory and Applications (Proc. Conf. Western Michigan University, Kalamazoo, Mich., 1972). Lecture Notes in Math., Vol. 303. Springer, Berlin (1972), pp. 179–181. Google Scholar 60 H. V. Kronk, Variations on a theorem of Pósa. The Many Facets of Graph Theory (Proc. Conf. Western Michigan University, Kalamazoo, Mich., 1968). Springer, Berlin (1969), pp. 193–197. Google Scholar 61 S. Kitamura, On the edge-chromatic number of a graph, Reports of the faculty of science and engineering. Saga Univ. Math. 3 (1975), 17–24. Google Scholar 62 V. G. Kane, and S. P. Mohanty, A lower bound on the number of vertices of a graph. Proc. Amer. Math. Soc. 72 (1978) 211–212. 10.2307/2042566 Web of Science®Google Scholar 63 M. Koman, On nonplanar graphs with the minimum number of vertices and a given girth. Kommentationes Math. Univ. Carolinae (Prague) 11 (1970) 9–17. Google Scholar 64 K. M. Koh, On the stability number of a graph. Nanta Math. 10 (1977) 53–57. Google Scholar 65 A. V. Kostǒcka, Upper bounds on the chromatic number of a graph in terms of its degree, density and girth. Soviet Math. Dokl. 18 (1977) 957–959. Google Scholar 66 V. Klee, and H. Quaife, Minimum graphs of specified diameter, connectivity and valence. I. Math. Operations Res. 1 (1976) 28–31. 10.1287/moor.1.1.28 Google Scholar 67 N. Linial, A lower bound for the circumference of a graph. Discrete Math. 15 (1976) 297–300. 10.1016/0012-365X(76)90031-5 Web of Science®Google Scholar 68 D. R. Lick, A class of point partition numbers. Recent Trends in Graph Theory (Proc. Conf. New York 1970). Lecture Notes in Mathematics, Vol. 186. Springer, Berlin (1971), pp. 185–190. Google Scholar 69 L. Lovász, Three short proofs in graph theory. J. Combinatorial Theory (B) 19 (1975) 269–271. 10.1016/0095-8956(75)90089-1 Web of Science®Google Scholar 70 L. Lovász, On covering of graphs. Theory of Graphs (Proc. Colloq. Tihany, 1966). Academic Press, New York (1968), pp. 231–236. Google Scholar 71 L. Lovász, Combinatorial Problems and Exercises. North-Holland, New York, (1979). Google Scholar 72 R. C. Laskar, and H. B. Walikar, On domination related concepts in graph theory. Lecture Notes in Math. 885. Springer-Verlag, Berlin (1980), 308–320. Google Scholar 73 J. Mitchem, An extension of Brooks' theorem to n-degenerate graphs. Discrete Math. 17 (1977) 291–298. 10.1016/0012-365X(77)90162-5 Web of Science®Google Scholar 74 M. Milgram, Bounds for the genus of graphs with given Betti number. J. Combinatorial Theory (B) 23 (1977) 227–233. 10.1016/0095-8956(77)90033-8 Web of Science®Google Scholar 75 B. R. Myers, and R. Liu, A lower bound on the chromatic number of a graph. Networks 1 (1971/72) 273–277. 10.1002/net.3230010306 Google Scholar 76 J. W. Moon, On the diameter of a graph. Michigan Math. J. 12 (1965) 349–351. 10.1307/mmj/1028999370 Web of Science®Google Scholar 77 M. Milgram, and P. Ungar, Bounds for the genus of graphs with given betti number. J. Combinatorial Theory B, 23 (1977) 227–233. 10.1016/0095-8956(77)90033-8 Web of Science®Google Scholar 78 E. A. Nordhaus, and J. W. Gaddum, On complementary graphs. Amer. Math. Monthly 63 (1956) 175–177. 10.2307/2306658 Google Scholar 79 O. Ore, On a graph theorem by Dirac. J. Combinatorial Theory 2 (1967), 383–392. 10.1016/S0021-9800(67)80036-X Google Scholar 80 D. Palumbiny, Sul numero minimo degli spigoli di un singramma di raggio e diametro equali a due. Accademia di Scienze e Lettre, Institute Lombardo (Rendiconti Scienze Matematiche) A106 (1972) 704–712. Google Scholar 81 J. Plesnik, Critical graphs of given diameter. Acta Facultatis Rerum Naturalium Universitatis Comenianae Mathematica XXX (1975) 71–93. Google Scholar 82 R. D. Ringeisen, Upper and lower imbeddable graphs. Graph Theory and Applications (Proc. of Conf. at Western Michigan Univ., May 10-13, 1972). Lecture Notes in Math., Vol. 303. Springer, Berlin (1972), pp. 261–268. Google Scholar 83 N. Sauer, The largest number of edges of a graph such that not more than g intersect in a point or more than n are independent. Combinatorial Mathematics and its Applications (Proc. Conf. Oxford, 1969). Academic Press, London (1971), pp. 253–257. Google Scholar 84 R. Singleton, There is no irregular Moore graph. Am. Math. Monthly 75 (1968) 42–43. 10.2307/2315106 Web of Science®Google Scholar 85 I. Tomescu, Sur les cycles élémentaires dans les graphes et hypergraphes k-chromatiques. Calcado 15 (1978) 1–15. 10.1007/BF02576041 Google Scholar 86 I. Tomescu, Le nombre maximal de colorations d'un graphe Hamiltonien. Discrete Math. 16 (1976) 353–359. 10.1016/S0012-365X(76)80010-6 Web of Science®Google Scholar 87 I. Tomescu, Problemes extremaux concernant le nombre des colorations des sommets d'un graphe fini. Combinatorial Programming: Methods and Applications (Proc. NATO Advanced Study Inst., Versailles, 1974), NATO Advanced Study Inst. Ser., Ser C: Math, and Phys. Sci., Vol. 19. Reidel, Dordrecht (1975) pp. 327–336. 10.1007/978-94-011-7557-9_17 Google Scholar 88 N. G. Vinnichenko, Upper bound to the number of edges of a graph with specified nondensity and all-contiguity numbers. Kibernetika (Kiev) 1 (1972) 159–161. Google Scholar 89 M. E. Watkins, A lower bound for the number of vertices of a graph. Am. Math. Monthly 74 (1967) 297. 10.2307/2316031 Web of Science®Google Scholar Citing Literature Volume15, Issue1Spring 1985Pages 73-107 ReferencesRelatedInformation
Referência(s)