# Some graphic uses of an even number of odd nodes

Annales de l'institut Fourier (1999)

- Volume: 49, Issue: 3, page 815-827
- ISSN: 0373-0956

## Access Full Article

top## Abstract

top## How to cite

topCameron, Kathie, and Edmonds, Jack. "Some graphic uses of an even number of odd nodes." Annales de l'institut Fourier 49.3 (1999): 815-827. <http://eudml.org/doc/75365>.

@article{Cameron1999,

abstract = {Vertex-degree parity in large implicit “exchange graphs” implies some EP theorems asserting the existence of a second object without evidently providing a polytime algorithm for finding a second object.},

author = {Cameron, Kathie, Edmonds, Jack},

journal = {Annales de l'institut Fourier},

keywords = {parity; hamiltonian; exchange graph; path; tree; flower; lollipop; circuit},

language = {eng},

number = {3},

pages = {815-827},

publisher = {Association des Annales de l'Institut Fourier},

title = {Some graphic uses of an even number of odd nodes},

url = {http://eudml.org/doc/75365},

volume = {49},

year = {1999},

}

TY - JOUR

AU - Cameron, Kathie

AU - Edmonds, Jack

TI - Some graphic uses of an even number of odd nodes

JO - Annales de l'institut Fourier

PY - 1999

PB - Association des Annales de l'Institut Fourier

VL - 49

IS - 3

SP - 815

EP - 827

AB - Vertex-degree parity in large implicit “exchange graphs” implies some EP theorems asserting the existence of a second object without evidently providing a polytime algorithm for finding a second object.

LA - eng

KW - parity; hamiltonian; exchange graph; path; tree; flower; lollipop; circuit

UR - http://eudml.org/doc/75365

ER -

## References

top- [1] A. G. THOMASON, Hamilton cycles and uniquely edge-colourable graphs, Annals of Discrete Mathematics, 3 (1978), 259-268. Zbl0382.05039MR80e:05077
- [2] S. TOIDA, Properties of an Euler graph, J. Franklin Institute, 295 (1973), 343-345. Zbl0341.05116MR48 #10906
- [3] J. A. BONDY and F. Y. HALBERSTAM, Parity theorems for paths and cycles in graphs, J. Graph Theory, 10 (1986), 107-115. Zbl0594.05041MR87f:05097
- [4] Kenneth A. BERMAN, Parity results on connected f-factors, Discrete Math., 59 (1986), 1-8. Zbl0594.05052MR87f:05127
- [5] Kathie CAMERON, Krawczyk's graphs show Thomason's algorithm for finding a second Hamilton cycle through a given edge in a cubic graph is exponential, Fifth Czech-Slovak Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague; SIAM Conference on Discrete Mathematics, Toronto; July 1998.
- [6] Douglas B. WEST, Pairs of adjacent hamiltonian circuits with small intersection, Studies in Applied Math., 59 (1978), 245-248. Zbl0398.90073MR80a:05141
- [7] N. J. A. SLOANE, Hamiltonian cycles in a graph of degree 4, J. Combinatorial Theory, 6 (1969), 311-312. Zbl0176.22402MR38 #5668
- [8] M. CHROBAK and S. POLJAK, On common edges in optimal solutions to traveling salesman and other optimization problems, Discrete Applied Math., 20 (1988), 101-111. Zbl0648.90082MR89h:90083
- [9] Christos H. PAPADIMITRIOU, On the complexity of the local structure of certain convex polytopes, Math. Programming, 14 (1978), 312-324. Zbl0376.90067
- [10] Kathie CAMERON and Jack EDMONDS, Existentially polytime theorems, DIMACS Series Discrete Mathematics and Theoretical Computer Science, 1 (1990), 83-99. Zbl0726.68062MR92i:68043
- [11] Christos H. PAPADIMITRIOU, On the complexity of the parity argument and other inefficient proofs of existence, J. Computer and System Sci., 48 (1994), 498-532. Zbl0806.68048MR95j:68061
- [12] Paul BEAME, Stephen COOK, Jeff EDMONDS, Russell Impagliazzo, Toniann Pitassi, The relative complexity of NP search problems, Proc. 27 th ACM STOC (1995), 303-314. Zbl0978.68526

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.