2024/07/01 by Diwan, Ajit A. · 1 citation
#05C35 05C22 05C38 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.01198
A weighted (directed) graph is a (directed) graph with integer weights assigned to its vertices and edges. The weight of a subgraph is the sum of weights of vertices and edges in the subgraph. The problem of determining the largest order f(k) of a weighted complete directed graph that does not contain a directed cycle of weight divisible by k, for an integer k ≥ 2, was raised by Alon and Krivelevich [J. Graph Theory 98 (2021) 623-629]. They showed that f(k) is O(klog k) and f(k) ≤ 2k-2 if k is prime. The best bounds known to us are f(k) ≤ 2k-2 for all k and f(k) < (3k-1)/2 for prime k. It is also known that f(k) ≥ k and this is believed to be the correct value. We prove that f(k) < k+2Ω(k), where Ω(k) is the number of prime factors, not necessarily distinct, in the prime factorization of k. We also show that any weighted undirected graph of minimum degree 2k-1 contains a cycle of weight divisible by k. This result is proved in the more general setting in which the weights are from a finite abelian group of order k, and the cycle has weight equal to the group identity. We conjecture that this holds for undirected graphs with minimum degree k+1.