Back to Search
Start Over
Proper-walk connection number of graphs
- Source :
- Bang-Jensen, J, Bellitto, T & Yeo, A 2021, ' Proper-walk connection number of graphs ', Journal of Graph Theory, vol. 96, no. 1-Special Issue: Ron Graham, pp. 137-159 . https://doi.org/10.1002/jgt.22609
- Publication Year :
- 2019
- Publisher :
- arXiv, 2019.
-
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 i.e. 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$.<br />Comment: 25 pages, 9 figures
- Subjects :
- FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
Existential quantification
Data_MISCELLANEOUS
connecting edge-colouring
0102 computer and information sciences
Characterization (mathematics)
01 natural sciences
Combinatorics
FOS: Mathematics
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
0101 mathematics
Time complexity
Connectivity
Mathematics
010102 general mathematics
proper connection by walks
Graph
010201 computation theory & mathematics
connected graph
Connection number
strongly connected digraph
Geometry and Topology
Combinatorics (math.CO)
Computer Science - Discrete Mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Bang-Jensen, J, Bellitto, T & Yeo, A 2021, ' Proper-walk connection number of graphs ', Journal of Graph Theory, vol. 96, no. 1-Special Issue: Ron Graham, pp. 137-159 . https://doi.org/10.1002/jgt.22609
- Accession number :
- edsair.doi.dedup.....7338b9b80d3ff556130e716f63417531
- Full Text :
- https://doi.org/10.48550/arxiv.1907.00428