An Extremal Characterization of the Incidence Graphs of Projective Planes期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

An Extremal Characterization of the Incidence Graphs of Projective Planes

Authors:	Gene Fiorini Felix Lazebnik

Affiliation:	(1) Department of Mathematics and Computer Science, Shippensburg University, Shippensburg, PA, 17257, U.S.A.;(2) Department of Mathematical Sciences, University of Delaware, Newark, DE, 19716, U.S.A

Abstract:	Let G be a 4-cycle free, bipartite graph on 2n vertices with partitions of equal cardinality n. Let c₆(G) denote the number of cycles of length 6 in G. We prove that for n 3, c₆(G) $frac{1} {3}left( {begin{array}{*{20}c} n 2 end{array} } right)(n - r_n )$ , where $r_n = frac{1} {2} + frac{{sqrt {4n - 3} }} {2}$ , with equality if and only if G is the incidence point-line graph of a projective plane.

Keywords:	point-line graph projective plane 4-cycle free maximum number of cycles extremal
本文献已被 SpringerLink 等数据库收录！