Relating ordinary and total domination in cubic graphs of large girth

doi:https://doi.org/10.1007/978-88-7642-475-5_9

Relating ordinary and total domination in cubic graphs of large girth

Simone Dantas,Felix Joos,Christian Löwenstein,Dieter Rautenbach,Deiwison S. Machado-2013-01-01-Scuola Normale Superiore eBooks

0

TL;DRAbstract

For a cubic graph G of order n, girth at least g, and domination number (1/4 + ε) for some ϵ ≥ 0, we show that the total domination number of G is at most 13/32n + O(n/g) + O(εn), which implies % MathType!MTEF!2!1!+- % feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaSaaaeaacq % aHZoWzcaWG0bGaaiikaiaadEeacaGGPaaabaGaeq4SdCMaaiikaiaa % dEeacaGGPaaaaiabgsMiJkaaigdacaGGUaGaaGyoaiaaikdacaaI0a % GaaG4naiaaikdacqGHRaWkcaaIWaWaaeWaaeaadaWcaaqaaiaad6ga % aeaacaWGNbaaaaGaayjkaiaawMcaaaaa!4A7E! $$ \frac{{\gamma t(G)}} {{\gamma (G)}} \leqslant 1.92472 + 0\left( {\frac{n} {g}} \right) $$ .

Chat with Paper

AI Agents for this Paper

For a cubic graph G of order n, girth at least g, and domination number (1/4 + ε) for some ϵ ≥ 0, we show that the total domination number of G is at most 13/32n + O(n/g) + O(εn), which implies % MathType!MTEF!2!1!+- % feaagaart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaSaaaeaacq % aHZoWzcaWG0bGaaiikaiaadEeacaGGPaaabaGaeq4SdCMaaiikaiaa % dEeacaGGPaaaaiabgsMiJkaaigdacaGGUaGaaGyoaiaaikdacaaI0a % GaaG4naiaaikdacqGHRaWkcaaIWaWaaeWaaeaadaWcaaqaaiaad6ga % aeaacaWGNbaaaaGaayjkaiaawMcaaaaa!4A7E! $$ \frac{{\gamma t(G)}} {{\gamma (G)}} \leqslant 1.92472 + 0\left( {\frac{n} {g}} \right) $$ .

Keywords

CombinatoricsDomination analysisGirth (graph theory)MathematicsGraphOrder (exchange)Cubic graphPhysics

Chat

Click to start Chat