Results 1 to 10 of about 413 (64)
Variantes del problema del cartero mixto que se pueden resolver usando programación lineal
Revista de Matemática: Teoría y Aplicaciones, 2012 Dada una gráfica mixta y conexa con costos en sus aristas y arcos, el problema del cartero mixto consiste en encontrar un circuito cerrado de la gráfica mixta que recorra sus aristas y arcos a costo mínimo. Se sabe que este problema es NP-duro.
Francisco Javier Zaragoza Martínez +1 more
doaj +2 more sources
Toughness, Forbidden Subgraphs, and Hamilton-Connected Graphs
Discussiones Mathematicae Graph Theory, 2022 A graph G is called Hamilton-connected if for every pair of distinct vertices {u, v} of G there exists a Hamilton path in G that connects u and v. A graph G is said to be t-tough if t·ω(G − X) ≤ |X| for all X ⊆ V (G) with ω(G − X) > 1. The toughness of G,
Zheng Wei, Broersma Hajo, Wang Ligong
doaj +1 more source
On Implicit Heavy Subgraphs and Hamiltonicity of 2-Connected Graphs
Discussiones Mathematicae Graph Theory, 2021 A graph G of order n is implicit claw-heavy if in every induced copy of K1,3 in G there are two non-adjacent vertices with sum of their implicit degrees at least n. We study various implicit degree conditions (including, but not limiting to, Ore- and Fan-
Zheng Wei, Wideł Wojciech, Wang Ligong
doaj +1 more source
On Order Prime Divisor Graphs of Finite Groups
Discussiones Mathematicae - General Algebra and Applications, 2021 The order prime divisor graph 𝒫𝒟(G) of a finite group G is a simple graph whose vertex set is G and two vertices a, b ∈ G are adjacent if and only if either ab = e or o(ab) is some prime number, where e is the identity element of the group G and o(x ...
Sen Mridul K. +2 more
doaj +1 more source
Asymptotically sharpening the $s$-Hamiltonian index bound [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 For a non-negative integer $s\le |V(G)|-3$, a graph $G$ is $s$-Hamiltonian if the removal of any $k\le s$ vertices results in a Hamiltonian graph. Given a connected simple graph $G$ that is not isomorphic to a path, a cycle, or a $K_{1,3}$, let $\delta(G)
Sulin Song +3 more
doaj +1 more source
2-generated Cayley digraphs on nilpotent groups have hamiltonian paths [PDF]
, 2011 Suppose G is a nilpotent, finite group. We show that if {a,b} is any 2-element generating set of G, then the corresponding Cayley digraph Cay(G;a,b) has a hamiltonian path.
Morris, Dave Witte
core +3 more sources
Forbidden Subgraphs for Existences of (Connected) 2-Factors of a Graph
Discussiones Mathematicae Graph Theory, 2023 Clearly, having a 2-factor in a graph is a necessary condition for a graph to be hamiltonian, while having an even factor in graph is a necessary condition for a graph to have a 2-factor.
Yang Xiaojing, Xiong Liming
doaj +1 more source
The H-force sets of the graphs satisfying the condition of Ore’s theorem
Open Mathematics, 2020 Let G be a Hamiltonian graph. A nonempty vertex set X⊆V(G)X\subseteq V(G) is called a Hamiltonian cycle enforcing set (in short, an H-force set) of G if every X-cycle of G (i.e., a cycle of G containing all vertices of X) is a Hamiltonian cycle.
Zhang Xinhong, Li Ruijuan
doaj +1 more source
Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs
Discussiones Mathematicae Graph Theory, 2022 In this paper, we completely characterize the connected forbidden subgraphs and pairs of connected forbidden subgraphs that force a 2-edge-connected (2-connected) graph to be collapsible.
Liu Xia, Xiong Liming
doaj +1 more source
Hamilton cycles in almost distance-hereditary graphs
Open Mathematics, 2016 Let G be a graph on n ≥ 3 vertices. A graph G is almost distance-hereditary if each connected induced subgraph H of G has the property dH(x, y) ≤ dG(x, y) + 1 for any pair of vertices x, y ∈ V(H).
Chen Bing, Ning Bo
doaj +1 more source