Weighted Eulerian extensions of random graphs
Main Article Content
Abstract
The Eulerian extension number of any graph H (i.e. the minimum number of edges needed to be added to make H Eulerian) is at least t(H), half the number of odd degree vertices of H. In this paper we consider weighted Eulerian extensions of a random graph G where we add edges of bounded weights and use an iterative probabilistic method to obtain sufficient conditions for the weighted Eulerian extension number of G to grow linearly with t(G). We derive our conditions in terms of the average edge probabilities and edge density and also show that bounded extensions are rare by estimating the skewness of a fixed weighted extension. Finally, we briefly describe a decomposition involving Eulerian extensions of G to convert a large dataset into small dissimilar batches.