Multithreshold multipartite graphs with small parts

DOI10.1016/J.DISC.2024.113979MaRDI QIDQ6419270zbMATH OpenOpenAlexFDO

Authors Teeradej Kittipassorn, Thanaporn Sumalroj

Publication date 1 December 2022

Full work available at URL https://doi.org/10.1016/j.disc.2024.113979

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Abstract: A graph is a $k$-threshold graph with thresholds $het{a}_1,het{a}_2,dots,het{a}_k$ if we can assign a real number $r_v$ to each vertex $v$ such that for any two distinct vertices $u$ and $v$, $uv$ is an edge if and only if the number of thresholds not exceeding $r_u+r_v$ is odd. The threshold number of a graph is the smallest $k$ for which it is a $k$-threshold graph. Multithreshold graphs were introduced by Jamison and Sprague as a generalization of classical threshold graphs. They asked for the exact threshold numbers of complete multipartite graphs. Recently, Chen and Hao solved the problem for complete multipartite graphs where each part is not too small, and they asked for the case when each part has size $3$. We determine the exact threshold numbers of $K_{3,3,dots,3}$, $K_{4,4,dots,4}$ and their complements $n{K}_3$, $n{K}_4$. This improves a result of Puleo.

Recommendations

• Multithreshold multipartite graphs
• Some results on multithreshold graphs
• Multithreshold graphs
• Threshold graphs
• On Universal Threshold Graphs

Cited in

(2)

• A note on the threshold numbers of cycles
• New developments on graph sum index

This page was built for publication: Multithreshold multipartite graphs with small parts

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