Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
Some localization Hamiltonian conditions - MaRDI portal

Deprecated: Use of MediaWiki\Skin\SkinTemplate::injectLegacyMenusIntoPersonalTools was deprecated in Please make sure Skin option menus contains `user-menu` (and possibly `notifications`, `user-interface-preferences`, `user-page`) 1.46. [Called from MediaWiki\Skin\SkinTemplate::getPortletsTemplateData in /var/www/html/w/includes/Skin/SkinTemplate.php at line 691] in /var/www/html/w/includes/Debug/MWDebug.php on line 372

Deprecated: Use of QuickTemplate::(get/html/text/haveData) with parameter `personal_urls` was deprecated in MediaWiki Use content_navigation instead. [Called from MediaWiki\Skin\QuickTemplate::get in /var/www/html/w/includes/Skin/QuickTemplate.php at line 131] in /var/www/html/w/includes/Debug/MWDebug.php on line 372

Some localization Hamiltonian conditions (Q1312923)

From MaRDI portal





scientific article; zbMATH DE number 495858
Language Label Description Also known as
English
Some localization Hamiltonian conditions
scientific article; zbMATH DE number 495858

    Statements

    Some localization Hamiltonian conditions (English)
    0 references
    26 January 1995
    0 references
    The following three results on Hamiltonicity have been obtained. Let \(G\) be a 2-connected graph with \(n (\geq 3)\) vertices. If \(| N(u) \cap N (v) |\) is greater than or equal to the size of the largest induced subgraph containing \(u\) and \(v\) and isomorphic to a star, whenever \(u,v \in V\), \(d(u,v) = 2\) and \(\max (d_ G(u), d_ G(v)) < {n \over 2}\), then \(G\) is Hamiltonian. If \(G\) is a graph of order \(n (\geq 3)\) such that for any vertex \(u\) and any \(x,y \in N (u) \cup \{u\}\) and \(xy \notin E(G)\), \(d_{N(u) \cup \{u\}} (x) + d_{N(u) \cup \{u\}} (y) \geq d_ G (u) + 1\), then \(G\) is Hamiltonian. (I think a condition on connectivity is necessary for this result.) Let \(G\) be a connected graph with \(n (\geq 3)\) vertices. If either \(G\) is complete or \(1 \leq \min \{{| S | \over \alpha (G[N(S)])}:S\) a separating set of \(G\}\), where \(\alpha (G[N(S)])\) is the independence number of the subgraph induced by \(N(S)\) in \(G\), then \(G\) is Hamiltonian. It is conjectured that a connected graph with \(n\) vertices such that for any vertex \(u\), the connectivity of the induced subgraph \(G[N(u) \cup \{u\}]\) is greater than or equal to its independence number \(\alpha (G[N(u) \cup \{u\}])\), is Hamiltonian. These are localizations of some well-known conditions for Hamiltonicity.
    0 references
    0 references
    Hamiltonicity
    0 references
    connectivity
    0 references
    independence number
    0 references
    0 references

    Identifiers