乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,24]],"date-time":"2023-08-24T11:19:19Z","timestamp":1692875959955},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T00:00:00Z","timestamp":1602720000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,5]]},"abstract":"Abstract<\/jats:title>Let

\n$\\gamma(G)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and

\n$${\\gamma _ \\circ }(G)$$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> denote the sizes of a smallest dominating set and smallest independent dominating set in a graph G, respectively. One of the first results in probabilistic combinatorics is that if G<\/jats:italic> is an n<\/jats:italic>-vertex graph of minimum degree at least d<\/jats:italic>, then

$$\\begin{equation}\\gamma(G) \\leq \\frac{n}{d}(\\log d + 1).\\end{equation}$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:p>In this paper the main result is that if G<\/jats:italic> is any n<\/jats:italic>-vertex d<\/jats:italic>-regular graph of girth at least five, then

$$\\begin{equation}\\gamma_(G) \\leq \\frac{n}{d}(\\log d + c)\\end{equation}$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula>for some constant c<\/jats:italic> independent of d<\/jats:italic>. This result is sharp in the sense that as

\n$d \\rightarrow \\infty$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, almost all d<\/jats:italic>-regular n<\/jats:italic>-vertex graphs G of girth at least five have

$$\\begin{equation}\\gamma_(G) \\sim \\frac{n}{d}\\log d.\\end{equation}$$<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:p>Furthermore, if G<\/jats:italic> is a disjoint union of

\n${n}\/{(2d)}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> complete bipartite graphs

\n$K_{d,d}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, then

\n${\\gamma_\\circ}(G) = \\frac{n}{2}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We also prove that there are n<\/jats:italic>-vertex graphs G of minimum degree d<\/jats:italic> and whose maximum degree grows not much faster than d<\/jats:italic> log d<\/jats:italic> such that

\n${\\gamma_\\circ}(G) \\sim {n}\/{2}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> as

\n$d \\rightarrow \\infty$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. Therefore both the girth and regularity conditions are required for the main result.<\/jats:p>","DOI":"10.1017\/s0963548320000279","type":"journal-article","created":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T06:46:04Z","timestamp":1602744364000},"page":"344-359","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Independent dominating sets in graphs of girth five"],"prefix":"10.1017","volume":"30","author":[{"given":"Ararat","family":"Harutyunyan","sequence":"first","affiliation":[]},{"given":"Paul","family":"Horn","sequence":"additional","affiliation":[]},{"given":"Jacques","family":"Verstraete","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,10,15]]},"reference":[{"key":"S0963548320000279_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309990186"},{"key":"S0963548320000279_ref11","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1016\/j.jctb.2007.02.006","article-title":"Large independent sets in regular graphs of large girth","volume":"97","author":"Lauer","year":"2007","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548320000279_ref14","unstructured":"[14] Payan, C. (1975) Sur le nombre d\u2019absorption d\u2019un graphe simple (in French). Proc. Colloq. Th. Graphes (Paris 1974), C.C.E.R.O 17 307\u2013317."},{"key":"S0963548320000279_ref3","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"Bollob\u00e1s","year":"2001"},{"key":"S0963548320000279_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"S0963548320000279_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(92)90070-E"},{"key":"S0963548320000279_ref8","doi-asserted-by":"crossref","unstructured":"[8] Godbole, A. and Hitczenko, P. (1998) Beyond the method of bounded differences. In Microsurveys in Discrete Probability (Princeton, NJ, 1997) ( Aldous, D. and Propp, J. , eds), pp. 43\u201358, AMS and DIMACS.","DOI":"10.1090\/dimacs\/041\/03"},{"key":"S0963548320000279_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579208"},{"key":"S0963548320000279_ref13","doi-asserted-by":"crossref","unstructured":"[13] McDiarmid, C. (1998) Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, Vol. 16 of Algorithms and Combinatorics, pp. 195\u2013248, Springer.","DOI":"10.1007\/978-3-662-12788-9_6"},{"key":"S0963548320000279_ref5","unstructured":"[5] Erd\u00f6s, P. and Lov\u00e1sz, L. (1975) Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and Finite Sets ( Hajnal, A. et al., eds), Vol. 11 of Colloquia Mathematica Societatis J\u00e1nos Bolyai, pp. 609\u2013627."},{"key":"S0963548320000279_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007431"},{"key":"S0963548320000279_ref18","doi-asserted-by":"crossref","unstructured":"[18] Zito, M. (2001) Greedy algorithms for minimisation problems in random regular graphs. In Proceedings of the 9th Annual European Symposium on Algorithms, Vol. 2161 of Lecture Notes in Computer Science, pp. 524\u2013536, Springer.","DOI":"10.1007\/3-540-44676-1_44"},{"key":"S0963548320000279_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90273-X"},{"key":"S0963548320000279_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548320000279_ref10","unstructured":"[10] Johansson, A. (1996) Asymptotic choice number for triangle free graphs. DIMACS Technical Report 91-95."},{"key":"S0963548320000279_ref1","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1006\/jctb.1999.1910","article-title":"Coloring graphs with sparse neighbourhoods","volume":"77","author":"Alon","year":"1999","journal-title":"J. Combin. Theory Ser. B"},{"key":"S0963548320000279_ref17","unstructured":"[17] Wormald, N. (1999) The differential equation method for random graph processes and greedy algorithms. In Lectures on Approximation and Randomized Algorithms ( Karo\u0144ski, M. and Pr\u00f6mel, H. J. , eds), pp. 73\u2013155, PWN."},{"key":"S0963548320000279_ref2","first-page":"3","article-title":"Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices (in Russian)","volume":"11","author":"Arnautov","year":"1974","journal-title":"Prikl. Mat. i Programmirovanie"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548320000279","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,13]],"date-time":"2021-04-13T11:59:40Z","timestamp":1618315180000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548320000279\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,15]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["S0963548320000279"],"URL":"https:\/\/doi.org\/10.1017\/s0963548320000279","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,15]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}