Extremed signed graphs for triangle

Publication date: 21 December 2022

Abstract: In this paper, we study the Tur'{a}n problem of signed graphs version. Suppose that

d o t G

is a connected unbalanced signed graph of order

n

with

e (d o t G)

edges and

e^{-} (d o t G)

negative edges, and let

h o (d o t G)

be the spectral radius of

d o t G .

The signed graph

d o t G^{s, t}

(

s + t = n - 2

) is obtained from an all-positive clique

(K_{n - 2}, +)

with

V (K_{n - 2}) = u_{1}, d o t s, u_{s}, v_{1}, d o t s, v_{t}

(

s, t g e 1

) and two isolated vertices

u

and

v

by adding negative edge

u v

and positive edges

u u_{1}, d o t s, u u_{s}, v v_{1}, d o t s, v v_{t} .

Firstly, we prove that if

d o t G

is

C_{3}^{-}

-free, then

e (d o t G) l e f r a c n (n - 1) 2 - (n - 2),

with equality holding if and only if

d o t G s i m d o t G^{s, t} .

Moreover,

e^{-} (d o t G^{s, t}) l e l f l o o r f r a c n - 2 2 f l o o r l c e i l f r a c n - 2 2 c e i l + n - 2,

with equality holding if and only if

d o t G^{s, t} = d o t G_{U}^{l f l o o r f r a c n - 2 2 f l o o r, l c e i l f r a c n - 2 2 c e i l},

where

d o t G_{U}^{l f l o o r f r a c n - 2 2 f l o o r, l c e i l f r a c n - 2 2 c e i l}

is obtained from

d o t G^{l f l o o r f r a c n - 2 2 f l o o r, l c e i l f r a c n - 2 2 c e i l}

by switching at vertex set

U = v, u_{1}, d o t s, u_{l f l o o r f r a c n - 2 2 f l o o r} .

Secondly, we prove that if

d o t G

is

C_{3}^{-}

-free, then

h o (d o t G) l e f r a c 12 (s q r t n^{2} - 8 + n - 4),

with equality holding if and only if

d o t G s i m d o t G^{1, n - 3} .

This page was built for publication: Extremed signed graphs for triangle