Some graphic uses of an even number of odd nodes
Cameron, Kathie ; Edmonds, Jack
Annales de l'Institut Fourier, Tome 49 (1999), p. 815-827 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

La parité des degrés dans les grands graphes d’échanges implicites implique des théorèmes EP qui assurent l’existence d’un second objet, sans assurer d’une manière évidente un algorithme polynomial pour trouver cet objet.

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.

@article{AIF_1999__49_3_815_0,
     author = {Cameron, Kathie and Edmonds, Jack},
     title = {Some graphic uses of an even number of odd nodes},
     journal = {Annales de l'Institut Fourier},
     volume = {49},
     year = {1999},
     pages = {815-827},
     doi = {10.5802/aif.1694},
     mrnumber = {2000f:05050},
     zbl = {0927.05052},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_1999__49_3_815_0}
}

Cameron, Kathie; Edmonds, Jack. Some graphic uses of an even number of odd nodes. Annales de l'Institut Fourier, Tome 49 (1999) pp. 815-827. doi : 10.5802/aif.1694. http://gdmltest.u-ga.fr/item/AIF_1999__49_3_815_0/

[1] A. G. Thomason, Hamilton cycles and uniquely edge-colourable graphs, Annals of Discrete Mathematics, 3 (1978), 259-268. | MR 80e:05077 | Zbl 0382.05039

[2] S. Toida, Properties of an Euler graph, J. Franklin Institute, 295 (1973), 343-345. | MR 48 #10906 | Zbl 0341.05116

[3] J. A. Bondy and F. Y. Halberstam, Parity theorems for paths and cycles in graphs, J. Graph Theory, 10 (1986), 107-115. | MR 87f:05097 | Zbl 0594.05041

[4] Kenneth A. Berman, Parity results on connected f-factors, Discrete Math., 59 (1986), 1-8. | MR 87f:05127 | Zbl 0594.05052

[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. | MR 80a:05141 | Zbl 0398.90073

[7] N. J. A. Sloane, Hamiltonian cycles in a graph of degree 4, J. Combinatorial Theory, 6 (1969), 311-312. | MR 38 #5668 | Zbl 0176.22402

[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. | MR 89h:90083 | Zbl 0648.90082

[9] Christos H. Papadimitriou, On the complexity of the local structure of certain convex polytopes, Math. Programming, 14 (1978), 312-324. | Zbl 0376.90067

[10] Kathie Cameron and Jack Edmonds, Existentially polytime theorems, DIMACS Series Discrete Mathematics and Theoretical Computer Science, 1 (1990), 83-99. | MR 92i:68043 | Zbl 0726.68062

[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. | MR 95j:68061 | Zbl 0806.68048

[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. | Zbl 0978.68526