乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:16:21Z","timestamp":1740104181452,"version":"3.37.3"},"reference-count":28,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2017,9,12]],"date-time":"2017-09-12T00:00:00Z","timestamp":1505174400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[2018,5]]},"abstract":"Abstract<\/jats:title>For a sequence d<\/jats:italic> of nonnegative integers, let and be the sets of all graphs and forests with degree sequence d<\/jats:italic>, respectively. Let , , , and where is the domination number and is the independence number of a graph G<\/jats:italic>. Adapting results of Havel and Hakimi, Rao showed in 1979 that can be determined in polynomial time. We establish the existence of realizations with , and with and that have strong structural properties. This leads to an efficient algorithm to determine for every given degree sequence d<\/jats:italic> with bounded entries as well as closed formulas for and .<\/jats:p>","DOI":"10.1002\/jgt.22189","type":"journal-article","created":{"date-parts":[[2017,9,12]],"date-time":"2017-09-12T07:06:48Z","timestamp":1505200008000},"page":"131-145","source":"Crossref","is-referenced-by-count":4,"title":["Smallest domination number and largest independence number of graphs and forests with given degree sequence"],"prefix":"10.1002","volume":"88","author":[{"given":"Michael","family":"Gentner","sequence":"first","affiliation":[{"name":"Institute of Optimization and Operations Research Ulm University Ulm Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8185-067X","authenticated-orcid":false,"given":"Michael A.","family":"Henning","sequence":"additional","affiliation":[{"name":"Department of Pure and Applied Mathematics University of Johannesburg Auckland Park 2006 South Africa"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7214-042X","authenticated-orcid":false,"given":"Dieter","family":"Rautenbach","sequence":"additional","affiliation":[{"name":"Institute of Optimization and Operations Research Ulm University Ulm Germany"}]}],"member":"311","published-online":{"date-parts":[[2017,9,12]]},"reference":[{"key":"e_1_2_5_2_1","first-page":"75","article-title":"Best monotone degree bounds for various graph parameters","volume":"192","author":"Bauer D.","year":"2008","journal-title":"Congr. Numerantium"},{"volume-title":"New results on the independence number","year":"1979","author":"Caro Y.","key":"e_1_2_5_3_1"},{"key":"e_1_2_5_4_1","first-page":"9","article-title":"Bounding the domination number of a tree in terms of its annihilation number","volume":"2","author":"Dehgardi N.","year":"2013","journal-title":"Trans. Comb."},{"key":"e_1_2_5_5_1","first-page":"21","article-title":"Bounding the rainbow domination number of a tree in terms of its annihilation number","volume":"2","author":"Dehgardi N.","year":"2013","journal-title":"Trans. Comb."},{"doi-asserted-by":"publisher","key":"e_1_2_5_6_1","DOI":"10.1016\/j.dam.2012.09.006"},{"doi-asserted-by":"publisher","key":"e_1_2_5_7_1","DOI":"10.1016\/j.dam.2014.05.037"},{"doi-asserted-by":"publisher","key":"e_1_2_5_8_1","DOI":"10.1016\/j.disc.2013.11.020"},{"doi-asserted-by":"publisher","key":"e_1_2_5_9_1","DOI":"10.1007\/s00493-013-2649-z"},{"doi-asserted-by":"publisher","key":"e_1_2_5_10_1","DOI":"10.1002\/jgt.3190150107"},{"key":"e_1_2_5_11_1","first-page":"19","article-title":"Some problems on graphic sequences","volume":"64","author":"Ferrara M.","year":"2013","journal-title":"Graph Theory Notes NY"},{"doi-asserted-by":"publisher","key":"e_1_2_5_12_1","DOI":"10.2140\/pjm.1957.7.1073"},{"doi-asserted-by":"publisher","key":"e_1_2_5_13_1","DOI":"10.1016\/j.dam.2016.01.040"},{"doi-asserted-by":"publisher","key":"e_1_2_5_14_1","DOI":"10.1137\/0110037"},{"key":"e_1_2_5_15_1","doi-asserted-by":"crossref","first-page":"477","DOI":"10.21136\/CPM.1955.108220","article-title":"A remark on the existence of finite graphs","volume":"80","author":"Havel V.","year":"1955","journal-title":"\u010cas. P\u011bstov\u00e1n\u00ed Mat"},{"volume-title":"Fundamentals of domination in graphs","year":"1998","author":"Haynes T. W.","key":"e_1_2_5_16_1"},{"key":"e_1_2_5_17_1","first-page":"535","volume-title":"Combinatorics, Graph Theory, and Algorithms","author":"K\u00e9zdy A. E.","year":"1999"},{"key":"e_1_2_5_18_1","article-title":"Graphs with equal independence and annihilation numbers","volume":"18","author":"Larson C. E.","year":"2011","journal-title":"Electr. J. Combin"},{"doi-asserted-by":"publisher","key":"e_1_2_5_19_1","DOI":"10.7151\/dmgt.1222"},{"doi-asserted-by":"publisher","key":"e_1_2_5_20_1","DOI":"10.1016\/0012-365X(91)90357-8"},{"unstructured":"R. Pepper On the annihilation number of a graph Proceedings of the 15th American Conference on Applied Mathematics World Scientific and Engineering Academy and Society 2009 pp. 217\u2013220.","key":"e_1_2_5_21_1"},{"key":"e_1_2_5_22_1","first-page":"251","article-title":"The clique number of a graph with a given degree sequence","volume":"4","author":"Rao R. A.","year":"1979","journal-title":"ISI Lect. Notes"},{"unstructured":"A. R.Rao An Erd\u0151s\u2010Gallai type result on the clique number of a realization of a degree sequence (unpublished).","key":"e_1_2_5_23_1"},{"doi-asserted-by":"publisher","key":"e_1_2_5_24_1","DOI":"10.4153\/CJM-1957-044-3"},{"volume-title":"Combinatorial optimization\u2014Polyhedra and efficiency","year":"2004","author":"Schrijver A.","key":"e_1_2_5_25_1"},{"key":"e_1_2_5_26_1","first-page":"1073","article-title":"Locating dominating sets and locating\u2010dominating sets","volume":"2","author":"Slater P. J.","year":"1995","journal-title":"Graph Theory, Combinatorics, and Applications, Proc. 7th Quadrennial Int. Conf. Theory Applic. Graphs"},{"doi-asserted-by":"publisher","key":"e_1_2_5_27_1","DOI":"10.1002\/(SICI)1097-0118(199605)22:1<89::AID-JGT12>3.0.CO;2-J"},{"key":"e_1_2_5_28_1","article-title":"A lower bound on the stability number of a simple graph","author":"Wei V. K.","year":"1981","journal-title":"Technical memorandum, TM 81\u201311217\u20109, Bell laboratories"},{"doi-asserted-by":"publisher","key":"e_1_2_5_29_1","DOI":"10.1016\/j.dam.2011.10.015"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.22189","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.22189","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T00:36:00Z","timestamp":1695688560000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.22189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,12]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["10.1002\/jgt.22189"],"URL":"https:\/\/doi.org\/10.1002\/jgt.22189","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"type":"print","value":"0364-9024"},{"type":"electronic","value":"1097-0118"}],"subject":[],"published":{"date-parts":[[2017,9,12]]}}}