Pith. sign in

REVIEW 1 cited by

The maximum number of triangles in graphs without large linear forests

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1812.09089 v2 pith:BYJDAGOJ submitted 2018-12-21 math.CO

classification math.CO
keywords deltabinomleftrightlinearmaximumnumberforest
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
abstract

Let $G$ be a graph on $n$ vertices. A linear forest is a graph consisting of vertex-disjoint paths and isolated vertices. A maximum linear forest of $G$ is a subgraph of $G$ with maximum number of edges, which is a linear forest. We denote by $l(G)$ this maximum number. Let $t=\left\lfloor (k-1)/2\right \rfloor$. Recently, Ning and Wang \cite{boning} proved that if $l(G)=k-1$, then for any $k<n$ \[ e(G) \leq \max \left\{\binom{k}{2},\binom{t}{2}+t (n - t)+ c \right\}, \] where $c=0$ if $k$ is odd and $c=1$ otherwise, and the inequality is tight. In this paper, we prove that if $l(G)=k-1$ and $\delta(G)=\delta$ ($\delta<\lfloor k/2 \rfloor$), then for any $k<n$ \[ e(G) \leq \max \left\{\binom{k-\delta}{2}+\delta(n-k+\delta),\binom{t}{2}+t\left(n-t\right)+c \right\}. \] When $\delta=0$, it reduces to Ning and Wang's result. Moreover, let $r_3(G)$ be the number of triangles in $G$. We prove that if $l(G)=k-1$ and $\delta(G)= \delta$, then for any $k<n$ \[ r_3(G)\leq \max \left\{\binom{k-\delta}{3}+\binom{\delta}{2}(n-k+\delta),\binom{t}{3}+\binom{t}{2}\left(n-t\right)+d \right\}. \] where $d=0$ if $k$ is odd and $d=t$ otherwise.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Survey of generalized Tur\'an problems -- counting subgraphs

    math.CO 2025-06 conditional novelty 2.0 of 10

    A survey of what is known about maximizing the count of one fixed subgraph in graphs that avoid another fixed subgraph.

Pith tools