Let ⊥ be a unitary polarity of a finite projective plane π of order q2. The unitary polarity graph is the graph with vertex set the points of π where two vertices x and y are adjacent if x∈y⊥. We show that a triangle-free induced subgraph of the unitary polarity graph of an arbitrary projective plane has at most (q4+q)∕2 vertices. When π is the Desarguesian projective plane PG(2,q2) and q is even, we show that the upper bound is asymptotically sharp, by providing an example on q4∕2 vertices. Finally, the case when π is the Figueroa plane is discussed.

Triangle-free induced subgraphs of the unitary polarity graph / Mattheus, Sam; Pavese, Francesco. - In: EUROPEAN JOURNAL OF COMBINATORICS. - ISSN 0195-6698. - STAMPA. - 72:(2018), pp. 83-96. [10.1016/j.ejc.2018.04.010]

Triangle-free induced subgraphs of the unitary polarity graph

Francesco Pavese
2018-01-01

Abstract

Let ⊥ be a unitary polarity of a finite projective plane π of order q2. The unitary polarity graph is the graph with vertex set the points of π where two vertices x and y are adjacent if x∈y⊥. We show that a triangle-free induced subgraph of the unitary polarity graph of an arbitrary projective plane has at most (q4+q)∕2 vertices. When π is the Desarguesian projective plane PG(2,q2) and q is even, we show that the upper bound is asymptotically sharp, by providing an example on q4∕2 vertices. Finally, the case when π is the Figueroa plane is discussed.
2018
https://doi.org/10.1016/j.ejc.2018.04.010
Triangle-free induced subgraphs of the unitary polarity graph / Mattheus, Sam; Pavese, Francesco. - In: EUROPEAN JOURNAL OF COMBINATORICS. - ISSN 0195-6698. - STAMPA. - 72:(2018), pp. 83-96. [10.1016/j.ejc.2018.04.010]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11589/176866
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact