TY - GEN
T1 - The Upper Bound on the Eulerian Recurrent Lengths of Complete Graphs Obtained by an IP Solver
AU - Jimbo, Shuji
AU - Maruoka, Akira
N1 - Funding Information:
supported by JSPS KAKENHI Grant Number
Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - If the degree of every vertex of a connected graph is even, then the graph has a circuit that contains all of edges, namely an Eulerian circuit. If the length of a shortest subcycle of an Eulerian circuit of a given graph is the largest, then the length is called the Eulerian recurrent length of the graph. For an odd integer n greater than or equal to 3, e(n) denotes the Eulerian recurrent length of the complete graph with n vertices. Values e(n) for all odd integers n with have been found by verification experiments using computers. If n is 7, 9, 11, or 13, then holds, for example. On the other hand, it has been shown that holds for any odd integer n greater than or equal to 15 in previous researches. In this paper, it is proved that holds for every odd integer n greater than or equal to 15. In the core part of the proof of the main theorem, an IP (integer programming) solver is used as the amount of computation is too large to be solved by hand.
AB - If the degree of every vertex of a connected graph is even, then the graph has a circuit that contains all of edges, namely an Eulerian circuit. If the length of a shortest subcycle of an Eulerian circuit of a given graph is the largest, then the length is called the Eulerian recurrent length of the graph. For an odd integer n greater than or equal to 3, e(n) denotes the Eulerian recurrent length of the complete graph with n vertices. Values e(n) for all odd integers n with have been found by verification experiments using computers. If n is 7, 9, 11, or 13, then holds, for example. On the other hand, it has been shown that holds for any odd integer n greater than or equal to 15 in previous researches. In this paper, it is proved that holds for every odd integer n greater than or equal to 15. In the core part of the proof of the main theorem, an IP (integer programming) solver is used as the amount of computation is too large to be solved by hand.
KW - Complete graphs
KW - Computer experiments
KW - Eulerian circuits
KW - Graph theory
KW - Shortest subcycles
UR - http://www.scopus.com/inward/record.url?scp=85062675847&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85062675847&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-10564-8_16
DO - 10.1007/978-3-030-10564-8_16
M3 - Conference contribution
AN - SCOPUS:85062675847
SN - 9783030105631
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 199
EP - 208
BT - WALCOM
A2 - Mukhopadhyaya, Krishnendu
A2 - Nakano, Shin-ichi
A2 - Das, Gautam K.
A2 - Mandal, Partha S.
PB - Springer Verlag
T2 - 13th International Conference and Workshop on Algorithms and Computations, WALCOM 2019
Y2 - 27 February 2019 through 2 March 2019
ER -