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

Abstract

top
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.

How to cite

top

Chou, 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. [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. [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. [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. [4] A. Benkouar, Y. Manoussakis and R. Saad, Edge-Colored Complete Graphs Containing Alternating Hamiltonian Cycles, submitted. Zbl1017.05068
  5. [5] A. Bialostocki and P. Dierker, On Simple Hamiltonian Cycles in a 2-Colored Complete Graph, Ars Combinatoria32(1991) 13-16. Zbl0751.05056MR1148908
  6. [6] B. Bollobàs and P. Erdös, Alternating Hamiltonian Cycles, Israel J. Mathematics23 (1976) 126-130. Zbl0325.05114MR411999
  7. [7] D. Cartwright and F. Harary, Structural balance: A generalisation of Heider's theory, Psychological Review63 (1956) 277-293. 
  8. [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. [9] C. Flament, Théorie des Graphes et Structures Sociales, Gauthier-Villars, Paris (1965). Zbl0169.26603MR221966
  10. [10] S. Fortune, J. Hopcroft and J. Wyllie, The Directed Subgraph Homeomorphism Problem, Theor. Comput. Science10 (1980) 111-121. Zbl0419.05028MR551599
  11. [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. [12] A. GyárfásVertex Coverings by Monochromatic Paths and Cycles, J. of Graph Theory7 (1983) 131-135. Zbl0511.05046MR693029
  13. [13] F. Heider, Attitudes and Cognitive Organization, Journal of Psychology21 (1946) 107-112. 
  14. [14] P. Hell, Y. Manoussakis and Zs. Tuza, Packing Problems in Edge-Colored Complete Graphs, Discrete Applied Mathematics52(1994) 295-306. Zbl0806.05054MR1287979
  15. [15] Y. Manoussakis, Alternating Paths in Edge-colored Complete Graphs, to appear in Discrete Applied Mathematics (1994). Zbl0819.05039MR1318749
  16. [16] Y. Manoussakis, M. Spyratos and Zs. Tuza, Cycles of Given Color Patterns, to appear in J. of Graph Theory (1995). Zbl0839.05056MR1368740
  17. [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. [18] H. Raynaud, Sur le Circuit Hamiltonien Bi-colore dans les Graphes Orientés, Periodica Math. Hungar.3 (1973) 289-297. Zbl0267.05114MR366739
  19. [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. [20] C. Whitehead, Alternating Cycles in Edge-Colored Graphs, J. of Graph Theory13 (1989) 387-391. Zbl0679.05046MR1010574

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.