ARTICLE
TITLE

Extremal Graph for Intersecting Odd Cycles

SUMMARY

An extremal graph for a graph HH on nn vertices is a graph on nn vertices with maximum number of edges that does not contain HH as a subgraph. Let Tn,rT_{n,r} be the Turán graph, which is the complete rr-partite graph on nn vertices with part sizes that differ by at most one. The well-known Turán Theorem states that Tn,rT_{n,r} is the only extremal graph for complete graph Kr+1K_{r+1}. Erdos et al. (1995) determined the extremal graphs for intersecting triangles and Chen et al. (2003) determined the maximum number of edges of the extremal graphs for intersecting cliques. In this paper, we determine the extremal graphs for intersecting odd cycles.

PAGES
pp. P2.29

 Articles related

Eric O. D. Andriantiana, Valisoa Razanajatovo Misanantenaina, Stephan Wagner    

The greedy tree G(D)\mathcal{G}(D) and the M\mathcal{M}-tree M(D)\mathcal{M}(D) are known to be extremal among trees with degree sequence DD with respect to various graph invariants. This paper provides a general theorem that covers a large family of inv... see more


Gabriel Coutinho    

In order to obtain perfect state transfer between two sites in a network of interacting qubits, their corresponding vertices in the underlying graph must satisfy a property called strong cospectrality. Here we determine the structure of graphs containing... see more


Reinhard Diestel    

Developing further Stein's recent notion of relative end degrees in infinite graphs, we investigate which degree assumptions can force a locally finite graph to contain a given finite minor, or a finite subgraph of given minimum or average degree. This i... see more


Robert R. Lewis    

This paper considers the degree-diameter problem for undirected circulant graphs. The focus is on extremal graphs of given (small) degree and arbitrary diameter. The published literature only covers graphs of up to degree 7. The approach used to establis... see more


Ioan Tomescu    

In this paper, the vertex-degree function index Hf(G) is considered when function f(x) belongs to four classes of functions determined by the following properties: strictly convex versus strictly concave and strictly increasing versus... see more