Category Graph Theory

Graph sphericity

The sphericity  of a graph is the smallest dimension such that there exists a mapping such that if and only if . The following theorem is due to Frankl and Maehara  and is a nice application of random projections. Here, . Theorem [Frankl-Maehara 1988]: Let be a graph with minimum adjacency eigenvalue where and suppose . […]

An observation on edge densities of the union of isomorphic copies of a fixed graph

Consider a fixed graph with vertices and edges respectively. Assume that is balanced which means that the maximum edge density among all possible subgraphs of is achieved from $H$. Take two copies of , call them and create a new graph . In case the two copies are edge disjoint then the edge density of […]

Edge-disjoint spanning subgraphs of large degree

Prove the following: you can always find in a simple undirected graph of minimum degree two spanning edge disjoint subgraphs of minimum degree at least . Give also an algorithmic procedure to find such subgraphs.