Abstract
We determine the maximum and minimum sizes of digraphs with a given clique numbers as well as the digraphs that attain these extremal sizes. The maximum and minimum transmissions of connected digraphs with given clique numbers are also determined.
Similar content being viewed by others
References
Akiyama J, Frankl P (1985) On the size of graphs with complete factors. J Graph Theory 9:197–201
Bondy JA, Murty USR (2008) Graph theory, GTM 244. Springer, Berlin
Huang Z, Zhan X (2012) Extremal digraphs whose walks with the same initial and terminal vertices have distinct lengths. Discret Math 312:2203–2213
Huang Z, Zhan X (2011) Digraphs that have at most one walk of a given length with the same endpoints. Discret Math 311:70–79
Joubert EJ (2013) Maximum sizes of graphs with given restrained domination numbers. Discret Appl Math 161:829–837
Li S, Song Y (2014) On the sum of all distances in bipartite graphs. Discret Appl Math 169:176–185
Plesník Ján (1984) On the sum of all distances in a graph or digraph. J Graph Theory 8:1–21
Sanchis LA (1991) Maximum number of edges in connected graphs with a given domination number. Discret Math 87:65–72
Sanchis LA (2000) On the number of edges in graphs with a given connected domination number. Discret Math 214:193–210
Vizing VG (1965) A bound on the external stability number of a graph. Dokl Akad Nauk SSSR 164:729–731
Volkmann L (2004) The maximum size of graphs with a unique \(k\)-factor. Combinatorica 24:531–540
Acknowledgments
The research of Huang was supported by the NSFC Grant 11401197 and a Fundamental Research Fund for the Central Universities. The research of Lin was supported by NSFC (No. 11401211), the China Postdoctoral Science Foundation (No. 2014M560303) and Fundamental Research Funds for the Central Universities (No. 222201414021).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Huang, Z., Lin, H. Sizes and transmissions of digraphs with a given clique number. J Comb Optim 31, 1642–1649 (2016). https://doi.org/10.1007/s10878-015-9850-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-015-9850-5