1Indian Statistical Institute, Chennai, India. 2Postdoctoral Researcher, Computer Science, University of Augsburg. 3Indian Institute of Technology Hyderabad
The electronic journal of combinatorics, Tome 32 (2025) no. 1
A graph $G$ on $n$ vertices is a threshold graph if there exist real numbers $a_1,a_2, \ldots,$$a_n$ and $b$ such that the zero-one solutions of the linear inequality $$\sum \limits_{i=1}^n a_i x_i \leq b$$ are exactly the characteristic vectors of the cliques of $G$. The threshold dimension of a graph $G$ is the minimum number of threshold graphs whose intersection yields $G$. We give tight or nearly tight upper bounds for the threshold dimension of a graph in terms of various graph parameters including treewidth, maximum degree, degeneracy, number of vertices, and vertex cover number. We also study threshold dimension of random graphs and graphs with high girth.
Classification :
05C70, 05C62, 05C80
Mots-clés :
threshold graph, threshold dimension of random graphs
Affiliations des auteurs :
Mathew C. Francis
1
;
Atrayee Majumder
2
;
Rogers Mathew
3
1
Indian Statistical Institute, Chennai, India.
2
Postdoctoral Researcher, Computer Science, University of Augsburg.
3
Indian Institute of Technology Hyderabad
@article{10_37236_12331,
author = {Mathew C. Francis and Atrayee Majumder and Rogers Mathew},
title = {Some bounds on the threshold dimension of graphs},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {1},
doi = {10.37236/12331},
zbl = {1559.05152},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12331/}
}
TY - JOUR
AU - Mathew C. Francis
AU - Atrayee Majumder
AU - Rogers Mathew
TI - Some bounds on the threshold dimension of graphs
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/12331/
DO - 10.37236/12331
ID - 10_37236_12331
ER -
%0 Journal Article
%A Mathew C. Francis
%A Atrayee Majumder
%A Rogers Mathew
%T Some bounds on the threshold dimension of graphs
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/12331/
%R 10.37236/12331
%F 10_37236_12331
Mathew C. Francis; Atrayee Majumder; Rogers Mathew. Some bounds on the threshold dimension of graphs. The electronic journal of combinatorics, Tome 32 (2025) no. 1. doi: 10.37236/12331
