The Optimization of Signed Trees

MaRDI QIDQ5869439zbMATH OpenFDO

Authors Alvaro Carbonero, Janelle Domantay, Karen Guthrie

Publication date 28 September 2022

Full work available at URL https://arxiv.org/abs/2109.01221, http://ajc.maths.uq.edu.au/pdf/84/ajc_v84_p111.pdf

zbMATH Keywords

setsdiametersigned graphsdegree

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Signed and weighted graphs (05C22)

Abstract: A signed graph $G$ is a graph where each edge is assigned a + (positive edge) or a - (negative edge). The signed degree of a vertex $v$ in a signed graph, denoted by $sdeg(v)$, is the number of positive edges incident to $v$ subtracted by the number of negative edges incident to $v$. Finally, we say $G$ realizes the set $D$ if: ${\displaystyle }$ D = {sdeg(v) ext{ : } vin V(G) }. ${\displaystyle }$ The topic of signed degree sets and signed degree sequences has been studied from many directions. In this paper, we study properties needed for signed trees to have a given signed degree set. We start by proving that $D$ is the signed degree set of a tree if and only if $1inD$ or $-1inD$. Further, for every valid set $D$, we find the smallest diameter that a tree must have to realize $D$. Lastly, for valid sets $D$ with nonnegative numbers, we find the smallest order that a tree must have to realize $D$.

Recommendations

• scientific article; zbMATH DE number 1210933
• Optimum lopsided binary trees
• scientific article; zbMATH DE number 3853098
• scientific article; zbMATH DE number 3914115
• Optimizing constrained subtrees of trees
• Optimal Search in Trees
• Optimal binary trees with order constraints
• On the cost of searching signature trees
• Optimal binary search trees
• Optimal binary search trees

Cites work

• A mathematical bibliography of signed and gain graphs and allied areas
• Net regular signed trees
• On co-regular signed graphs
• On composition of signed graphs
• On the notion of balance of a signed graph
• Signed degree sequences in signed multipartite graphs
• Signed degree sequences of signed graphs
• Signed degree sets in signed graphs

Cited in

(1)

• Signed degree sets in signed graphs

This page was built for publication: The Optimization of Signed Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5869439)