Some graphic uses of an even number of odd nodes

DOI10.5802/aif.1694zbMath0927.05052OpenAlexW2499374790WikidataQ63392983 ScholiaQ63392983MaRDI QIDQ1296145

Kathie Cameron, Jack Edmonds

Publication date: 12 July 1999

Published in: Annales de l'Institut Fourier (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=AIF_1999__49_3_815_0

zbMATH Keywords

treepathcircuitparityexchange graphhamiltonianflowerlollipop

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Related Items (8)

Cycles containing all the odd-degree vertices ⋮ Euler Complexes ⋮ Understanding PPA-completeness ⋮ A parity theorem about trees with specified degrees ⋮ Exponentiality of the exchange algorithm for finding another room-partitioning ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A PPA parity theorem about trees in a bipartite graph

Cites Work

• Unnamed Item
• Unnamed Item
• Parity results on connected f-factors
• On common edges in optimal solutions to traveling salesman and other optimization problems
• Properties of a Euler graph
• On the complexity of the parity argument and other inefficient proofs of existence
• Parity theorems for paths and cycles in graphs
• The adjacency relation on the traveling salesman polytope is NP-Complete
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Pairs of Adjacent Hamiltonian Circuits with Small Intersection
• Hamiltonian cycles in a graph of degree 4

This page was built for publication: Some graphic uses of an even number of odd nodes