# Paths through fixed vertices in edge-colored graphs

W. S. Chou; Y. Manoussakis; O. Megalakaki; M. Spyratos; Zs. Tuza

Mathématiques et Sciences Humaines (1994)

- Volume: 127, page 49-58
- ISSN: 0987-6936

## Access Full Article

top## Abstract

top## How to cite

topChou, W. S., et al. "Paths through fixed vertices in edge-colored graphs." Mathématiques et Sciences Humaines 127 (1994): 49-58. <http://eudml.org/doc/94457>.

@article{Chou1994,

abstract = {We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length s+t such that s consecutive edges are in one color and t consecutive edges are in another color.},

author = {Chou, W. S., Manoussakis, Y., Megalakaki, O., Spyratos, M., Tuza, Zs.},

journal = {Mathématiques et Sciences Humaines},

keywords = {edge-coloured paths; alternating paths; paths through specified vertices},

language = {eng},

pages = {49-58},

publisher = {Ecole des hautes-études en sciences sociales},

title = {Paths through fixed vertices in edge-colored graphs},

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

volume = {127},

year = {1994},

}

TY - JOUR

AU - Chou, W. S.

AU - Manoussakis, Y.

AU - Megalakaki, O.

AU - Spyratos, M.

AU - Tuza, Zs.

TI - Paths through fixed vertices in edge-colored graphs

JO - Mathématiques et Sciences Humaines

PY - 1994

PB - Ecole des hautes-études en sciences sociales

VL - 127

SP - 49

EP - 58

AB - We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length s+t such that s consecutive edges are in one color and t consecutive edges are in another color.

LA - eng

KW - edge-coloured paths; alternating paths; paths through specified vertices

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

ER -

## References

top- [1] M. Bánkfalvi and Z. Bánkfalvi, Alternating Hamiltonian Circuits in 2-colored Complete Graphs, Theory of Graphs, Akadémiai Kiadô, Budapest (1968) 11-18. Zbl0159.54202
- [2] A. Benkouar, Y. Manoussakis, V. Paschos and R. Saad, On the Complexity of Some Hamiltonian and Eulerian Problems in Edge-colored Complete Graphs, Lecture Notes in Computer Sciences (W.L. Hsu and R. C. T. Lee Eds) Vol. 557 (1991) 190-198, Springer Verlag (also to appear in RAIRO). Zbl0868.90128
- [3] A. Benkouar, Y. Manoussakis and R. Saad, Alternating Cycles Through Given Vertices in Edge-Colored Complete Graphs, to appear in JCCCM (1994). Zbl0813.05042MR1301222
- [4] A. Benkouar, Y. Manoussakis and R. Saad, Edge-Colored Complete Graphs Containing Alternating Hamiltonian Cycles, submitted. Zbl1017.05068
- [5] A. Bialostocki and P. Dierker, On Simple Hamiltonian Cycles in a 2-Colored Complete Graph, Ars Combinatoria32(1991) 13-16. Zbl0751.05056MR1148908
- [6] B. Bollobàs and P. Erdös, Alternating Hamiltonian Cycles, Israel J. Mathematics23 (1976) 126-130. Zbl0325.05114MR411999
- [7] D. Cartwright and F. Harary, Structural balance: A generalisation of Heider's theory, Psychological Review63 (1956) 277-293.
- [8] C.C. Chen and D.E. Daykin, Graphs With Hamiltonian Cycles Having Adjacent Lines of Different Colors, J. Combinatorial Theory (B) 21 (1976) 135-139. Zbl0287.05106MR422070
- [9] C. Flament, Théorie des Graphes et Structures Sociales, Gauthier-Villars, Paris (1965). Zbl0169.26603MR221966
- [10] S. Fortune, J. Hopcroft and J. Wyllie, The Directed Subgraph Homeomorphism Problem, Theor. Comput. Science10 (1980) 111-121. Zbl0419.05028MR551599
- [11] J.W. Grossman and R. Häggkvist, Alternating Cycles in Edge-Partitioned Graphs, J. Combinatorial Theory (B) 34 (1983) 77-81. Zbl0491.05039MR701173
- [12] A. GyárfásVertex Coverings by Monochromatic Paths and Cycles, J. of Graph Theory7 (1983) 131-135. Zbl0511.05046MR693029
- [13] F. Heider, Attitudes and Cognitive Organization, Journal of Psychology21 (1946) 107-112.
- [14] P. Hell, Y. Manoussakis and Zs. Tuza, Packing Problems in Edge-Colored Complete Graphs, Discrete Applied Mathematics52(1994) 295-306. Zbl0806.05054MR1287979
- [15] Y. Manoussakis, Alternating Paths in Edge-colored Complete Graphs, to appear in Discrete Applied Mathematics (1994). Zbl0819.05039MR1318749
- [16] Y. Manoussakis, M. Spyratos and Zs. Tuza, Cycles of Given Color Patterns, to appear in J. of Graph Theory (1995). Zbl0839.05056MR1368740
- [17] R. Norman and F.R. Oberts, A Derivation of a Measure of Relative Balance for Social Structures and a Caracterization of Extensive Ratio Systems, Journal of Mathematical Psychology9 (1972) 66-91. Zbl0233.92006MR293041
- [18] H. Raynaud, Sur le Circuit Hamiltonien Bi-colore dans les Graphes Orientés, Periodica Math. Hungar.3 (1973) 289-297. Zbl0267.05114MR366739
- [19] F. Roberts, Graph Theory and its Applications to Problems of Society, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAMPhiladelphia, 1978. Zbl0452.05001MR508050
- [20] C. Whitehead, Alternating Cycles in Edge-Colored Graphs, J. of Graph Theory13 (1989) 387-391. Zbl0679.05046MR1010574

## Citations in EuDML Documents

top## NotesEmbed ?

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