2023/05/25 by Ramu, Mohan, Kureethara, Joseph Varghese
#05C22 #05C78 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2305.16451
For a given graph G, let f:V(G)→ \1,2,…,n\ be a bijective mapping. For a given edge uv ∈ E(G), σ(uv)=+, if f(u) and f(v) have the same parity and σ(uv)=-, if f(u) and f(v) have opposite parity. The resultant signed graph is called a parity signed graph and the mapping σ is called a parity signature of G. Let us denote a parity signed graph S=(G,σ) by Gσ. Let E-(Gσ) be a set of negative edges in a parity signed graph and let Si(G) be the set of all parity signatures for the underlying graph G. We define the rna number of G as σ-(G)=min\|E-(Gσ)|:σ∈ Si(G)\. In this paper, we prove a non-trivial upper bound in the case of trees: σ-(T)≤ \lceil(n)/(2)\rceil, where T is a tree of order n+1. We have found families of trees whose rna numbers are bounded above by \lceil\fracΔ2\rceil and also we have shown that for any i≤ \lceil(n)/(2)\rceil, there exists a tree T (of order n+1) with σ-(T)=i. This paper gives a characterization of graphs with rna number 1 in terms of its spanning trees and also a characterization of graphs with rna number 2.