ARTICLE

Proper-walk connection number of graphs

Corresponding Author

Jørgen Bang-Jensen

[email protected]

orcid.org/0000-0001-5783-7125

Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark

Correspondence Jørgen Bang-Jensen, Department of Mathematics and Computer Science, University of Southern Denmark, Odense DK5230, Denmark.

Email: [email protected]

Search for more papers by this author

Thomas Bellitto,

Thomas Bellitto

Institute of Informatics, Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Warsaw, Poland

Search for more papers by this author

Anders Yeo,

Anders Yeo

Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark

Department of Pure and Applied Mathematics, University of Johannesburg, Johannesburg, South Africa

Search for more papers by this author

Jørgen Bang-Jensen,

Corresponding Author

Jørgen Bang-Jensen

[email protected]

orcid.org/0000-0001-5783-7125

Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark

Correspondence Jørgen Bang-Jensen, Department of Mathematics and Computer Science, University of Southern Denmark, Odense DK5230, Denmark.

Email: [email protected]

Search for more papers by this author

Thomas Bellitto,

Thomas Bellitto

Institute of Informatics, Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Warsaw, Poland

Search for more papers by this author

Anders Yeo,

Anders Yeo

Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark

Department of Pure and Applied Mathematics, University of Johannesburg, Johannesburg, South Africa

Search for more papers by this author

We dedicate this paper to Ron Graham whose enormous energy, friendly attitude, open mindedness and countless contributions to science has always been a great inspiration

First published: 30 June 2020

https://doi.org/10.1002/jgt.22609

Citations: 4

Share a link

Email
Wechat
Bluesky

Abstract

This paper studies the problem of proper-walk connection number: given an undirected connected graph, our aim is to colour its edges with as few colours as possible so that there exists a properly coloured walk between every pair of vertices of the graph, that is, a walk that does not use consecutively two edges of the same colour. The problem was already solved on several classes of graphs but still open in the general case. We establish that the problem can always be solved in polynomial time in the size of the graph and we provide a characterization of the graphs that can be properly connected with $k$ colours for every possible value of $k$ .

REFERENCES

1M. Ahmed and A. Lubiw, Shortest paths avoiding forbidden subpaths. Proceedings of 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, 2009, pp. 63–74.
Google Scholar
2T. Bellitto and B. Bergougnoux., On minimum connecting transition sets in graphs. Proceedings of Graph-Theoretic Concepts in Computer Science—44th International Workshop, WG 2018, Cottbus, Germany, June 27–29, 2018, pp. 40–51.
10.1007/978-3-030-00256-5_4
Google Scholar
3J. Bang-Jensen et al., Antistrong digraphs, J. Comb. Theory, Ser. B 122 (2017), 68–90.
10.1016/j.jctb.2016.05.004
Web of Science® Google Scholar
4C. Brause, T. D. Doan, and I. Schiermeyer, On the minimum degree and the proper connection number of graphs, Electron. Note. Discrete Math. 55 (2016), 109–112.
10.1016/j.endm.2016.10.028
Google Scholar
5C. Brause, T. D. Doan, and I. Schiermeyer, Proper connection number 2, connectivity, and forbidden subgraphs, Electron. Note. Discrete Math. 55 (2016), 105–108.
10.1016/j.endm.2016.10.027
Google Scholar
6C. Brause, T. D. Doan, and I. Schiermeyer, Minimum degree conditions for the proper connection number of graphs, Graph Combinator. 33 (2017), no. 4, 833–843.
10.1007/s00373-017-1796-1
Web of Science® Google Scholar
7T. Bellitto. Separating codes and traffic monitoring. Selected papers presented at the 11th International Conference on Algorithmic Aspects of Information and Management (AAIM 2016). (Theoretical Computer Science, 717:73–85, 2018).
Google Scholar
8V. Borozan et al., Proper connection of graphs, Discrete Math. 312 (2012), no. 17, 2550–2560.
10.1016/j.disc.2011.09.003
Web of Science® Google Scholar
9J. Bang-Jensen, and G. Z. Gutin, Digraphs: theory, algorithms and applications, 2nd ed., Springer, London, 2009.
10.1007/978-1-84800-998-1
Google Scholar
10C. C. Chen and D. E. Daykin, Graphs with hamiltonian cycles having adjacent lines different colors, J. Comb. Theory, Ser. B 21 (1976), no. 2, 135–139.
10.1016/0095-8956(76)90053-8
Web of Science® Google Scholar
11G. Ducoffe, R. Marinescu-Ghemeci, and A. Popa, On the (di)graphs with (directed) proper connection number two, Electron. Note. Discrete Math. 62 (2017), 237–242.
10.1016/j.endm.2017.10.041
Google Scholar
12D. Dorninger, Hamiltonian circuits determining the order of chromosomes, Discrete Appl. Math. 50 (1994), no. 2, 159–168.
10.1016/0166-218X(92)00171-H
Web of Science® Google Scholar
13G. Gutin, and E. J. Kim, Properly coloured cycles and paths: Results and open problems, Graph Theory Computational Intelligence and Thought, Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday, 2009, pp. 200–208.
10.1007/978-3-642-02029-2_19
Google Scholar
14W. Goddard and R. Melville, Properly colored trails, paths, and bridges, J. Comb. Optim. 35 (2018), no. 2, 463–472.
10.1007/s10878-017-0191-4
Web of Science® Google Scholar
15F. Huang and J. Yuan, On strong proper connection number of cubic graphs, Discrete Appl. Math. 265 (2019), 104–119.
10.1016/j.dam.2019.03.014
Web of Science® Google Scholar
16E. Laforge, C. Lumduanhom, and P. Zhang, Characterizations of graphs having large proper connection numbers, Discussion. Math. Graph Theory. 36 (2016), no. 2, 439–453.
10.7151/dmgt.1867
Web of Science® Google Scholar
17R. Melville and W. Goddard, Coloring graphs to produce properly colored walks, Graph. Combinator. 33 (2017), no. 5, 1271–1281.
10.1007/s00373-017-1843-y
Web of Science® Google Scholar
18R. Saad, Finding a longest alternating cycle in a 2-edge-coloured complete graph is in RP, Combinator. Probability Comput. 5 (1996), 297–306.
10.1017/S0963548300002054
Google Scholar
19B. Sudakov, Robustness of graph properties, Surveys in Combinatorics 2017 ( A. Claesson, M. Dukes, S. Kitaev, D. Manlove, and K. Meeks, eds.), Cambridge University Press, Cambridge, 2017, pp. 372–408.
10.1017/9781108332699.009
Google Scholar

Citing Literature

Volume96, Issue1

Special Issue:Ron Graham

January 2021

Pages 137-159

Proper-walk connection number of graphs

Abstract

REFERENCES

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Proper-walk connection number of graphs

Abstract

REFERENCES

Citing Literature

References

Related

Information