Name
Abstract | ||
|---|---|---|
A basic pigeonhole principle insures an existence of two objects of the same type if the number of objects is larger than the number of types. Can such a principle be extended to a more complex combinatorial structure? Here, we address such a question for graphs. We call two disjoint subsets A,B of vertices twins if they have the same cardinality and induce subgraphs of the same size. Let t(G) be the largest k such that G has twins on k vertices each. We provide the bounds on t(G) in terms of the number of edges and vertices using discrepancy results for induced subgraphs. In addition, we give conditions under which t(G)=|V(G)|/2 and show that if G is a forest then t(G)=|V(G)|/2-1. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.ejc.2014.01.007 | Eur. J. Comb. |
Keywords | Field | DocType |
vertices twin,largest k,induced subgraphs,basic pigeonhole principle,complex combinatorial structure,discrepancy result | Discrete mathematics,Graph,Combinatorics,Disjoint sets,Vertex (geometry),Cardinality,Mathematics,Pigeonhole principle | Journal |
Volume | ISSN | Citations |
39, | European J. Combin 39 (2014), 188--197 | 1 |
PageRank | References | Authors |
0.37 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maria Axenovich | 1 | 209 | 33.90 |
| Ryan Martin | 2 | 144 | 14.43 |
| torsten ueckerdt | 3 | 141 | 26.26 |