Self-similarity of graphs

Details Self-similarity of graphs Self-similarity of graphs

2012-01-04

arxiv.org/abs/1201.0924v1

Mathematics

Combinatorics

15 pages

Scientific paper

An old problem raised independently by Jacobson and Sch\"onheim asks to determine the maximum $s$ for which every graph with $m$ edges contains a pair of edge-disjoint isomorphic subgraphs with $s$ edges. In this paper we determine this maximum up to a constant factor. We show that every $m$-edge graph contains a pair of edge-disjoint isomorphic subgraphs with at least $c (m\log m)^{2/3}$ edges for some absolute constant $c$, and find graphs where this estimate is off only by a multiplicative constant. Our results improve bounds of Erd\H{o}s, Pach, and Pyber from 1987.

Affiliated with

Also associated with

No associations

Rating

Self-similarity of graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Self-similarity of graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Self-similarity of graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-156757