On subgraph number independence in trees |
| |
Authors: | RL Graham E Szemerédi |
| |
Institution: | Bell Laboratories, Murray Hill, New Jersey 07974 USA;The Hungarian Academy of Sciences, Budapest, Hungary |
| |
Abstract: | For finite graphs F and G, let NF(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If and are families of graphs, it is natural to ask then whether or not the quantities NF(G), F∈, are linearly independent when G is restricted to . For example, if = {K1, K2} (where Kn denotes the complete graph on n vertices) and is the family of all (finite) trees, then of course NK1(T) ? NK2(T) = 1 for all T∈. Slightly less trivially, if = {Sn: n = 1, 2, 3,…} (where Sn denotes the star on n edges) and again is the family of all trees, then Σn=1∞(?1)n+1NSn(T)=1 for all T∈. It is proved that such a linear dependence can never occur if is finite, no F∈ has an isolated point, and contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|