Premium
An extremal problem for paths in bipartite graphs
Author(s) -
Gyárfás A.,
Rousseau C. C.,
Schelp R. H.
Publication year - 1984
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190080109
Subject(s) - combinatorics , mathematics , bipartite graph , graph , complete bipartite graph , path (computing) , pancyclic graph , discrete mathematics , 1 planar graph , chordal graph , computer science , programming language
Abstract A formula is found for the maximum number of edges in a graph G ⊆ K(a, b) which contains no path P 2 l for l > c. A similar formula is found for the maximum number of edges in G ⊆ K(a, b) containing no P 2 l + 1 for l > c . In addition, all extremal graphs are determined.