Two path extremal graphs and an application to a Ramsey-type problem
type: Item
instance of: scholarly article
title: Two path extremal graphs and an application to a Ramsey-type problem
zbMATH Open document ID: 0924.05042
DOI: 10.1016/S0012-365X(98)00195-2
published in: Discrete Mathematics
publication date: 1999-11-03T00:00:00Z
review text: In any undirected simple graph \(G\), \(p_2(G)\) denotes the number of paths of length 2. \(G\) is a \((v,e)\)-graph if it has precisely \(v\) vertices and \(e\) edges; \(g(v,e)=\max\{p_2(G):G\) is a \((v,e)\)-graph\(\}\); those graphs for which the maximum is attained are called \((v,e)\)-extremal or 2-path extremal. From the author's introduction and his abstract: ``In this paper we completely classify all graphs attaining these extrema. As an application we show that, if \(H\) is a connected graph with 3 edges, the number of occurrences of \(H\) as a subgraph in \(G\) or \(G^c\) is maximized (over the class of \((v,e)\)-graphs) if and only if \(p_2(G)=g(v,e)\dots\). In [Extremal graphic sequences, Recent studies in graph theory, 159-176, Vishwa, Gulbarga, (1989)] \textit{J. W. Kennedy, P. N. Nikolakos}, and \textit{L. W. Quintas} examined degree sequences of graphs in order to maximize and minimize \(p_2(G)\) over various families of graphs \(\dots\). For some pairs \(v\) and \(e\) they constructed a \((v,e)\)-graph \(G\) such that \(p_2(G)=g(v,e)\). However, their construction does not always yield a \((v,e)\)-extremal graph, as they claimed, so their computation of \(g(v,e)\) is incorrect \(\dots\). In [The degree variance: An index of graph heterogeneity, Social Networks 3, No. 3, 163-174 (1981/82)] \textit{T. A. B. Snijders} \(\dots\) computes \(g(v,e)\) by describing two classes of \((v,e)\)-graphs and showing that one of them always contains an extremal graph. Prior to Snijders' work, in [Graphs with maximal number of adjacent pairs of edges, Acta Math. Acad. Sci. Hung. 32, 97-120 (1978; Zbl 0386.05036)] \textit{R. Ahlswede} and \textit{G. O. H. Katona} had found the same two classes and given some bounds for determining which of the two classes must contain an extremal graph. However, none of these authors classified all of the extremal graphs, a main new result of this paper \(\dots\). As an application we consider 2-colourings of the edges of \(K_v\), wh…
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 1321766
zbMATH Keywords: paths
zbMATH Keywords: extremal graph
zbMATH Keywords: monochromatic subgraph
author: Owen D. Byer
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Graphs with maximal number of adjacent pairs of edges
cites work: Q3852212
cites work: Q5422499
cites work: Q5724802
cites work: Comparisons of Bayesian estimation procedures for two-way contingency tables without interaction
description: scientific article; zbMATH DE number 1321766