Ben Barber, Daniela Kühn, Allan Lo and Deryk Osthus, Advances in Mathematics, Volume 288, 22 January 2016, Pages 337–385 PDF When can the edge set of a graph be partitioned into triangles? Two obvious necessary conditions are that the total number of edges is divisible by 3 and the degree of every vertex is even. We …
Tag: graphs
Random walks on quasirandom graphs
Ben Barber and Eoin Long, The Electronic Journal of Combinatorics, 20(4) (2013), #P25 PDF Take a long (proportional to ) random walk in a quasirandom graph . Must the subgraph of edges traversed by be quasirandom? We’d like to say yes, for the following reason: visits every vertex about the same number of times, so we …