Geodesic
Weakly threshold graphs
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1.

Voir la notice de l'article provenant de la source Episciences

We define a weakly threshold sequence to be a degree sequence $d=(d_1,\dots,d_n)$ of a graph having the property that $\sum_{i \leq k} d_i \geq k(k-1)+\sum_{i > k} \min\{k,d_i\} - 1$ for all positive $k \leq \max\{i:d_i \geq i-1\}$. The weakly threshold graphs are the realizations of the weakly threshold sequences. The weakly threshold graphs properly include the threshold graphs and satisfy pleasing extensions of many properties of threshold graphs. We demonstrate a majorization property of weakly threshold sequences and an iterative construction algorithm for weakly threshold graphs, as well as a forbidden induced subgraph characterization. We conclude by exactly enumerating weakly threshold sequences and graphs. 
@article{DMTCS_2018_20_1_a15,
     author = {Barrus, Michael D.},
     title = {Weakly threshold graphs},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2018},
     doi = {10.23638/DMTCS-20-1-15},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-15/}
}
TY  - JOUR
AU  - Barrus, Michael D.
TI  - Weakly threshold graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2018
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-15/
DO  - 10.23638/DMTCS-20-1-15
LA  - en
ID  - DMTCS_2018_20_1_a15
ER  - 
%0 Journal Article
%A Barrus, Michael D.
%T Weakly threshold graphs
%J Discrete mathematics & theoretical computer science
%D 2018
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-15/
%R 10.23638/DMTCS-20-1-15
%G en
%F DMTCS_2018_20_1_a15
Barrus, Michael D. Weakly threshold graphs. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1. doi : 10.23638/DMTCS-20-1-15. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-15/

Cité par Sources :