The maximum outdegree power of complete k-partite oriented graphs

Chentao Xu, Zhe You, Liwen Zhang and Minghong Zhou

Applied Mathematics and Computation, 2022, vol. 433, issue C

Abstract: Suppose that Gσ is an oriented graph with order n and orientation σ. For d1+≥d2+≥⋯≥dn+, the outdegree sequence of Gσ is denoted by (d1+,d2+,…,dn+). Similar to the definition of the degree power for a simple graph, define the outdegree power for an oriented graph Gσ by ∂q+(Gσ)=∑i=1n(di+)q where q is a positive integer. Obviously, ∂1+(Gσ)=|E(G)|. Denote by G(G) the set of oriented graphs whose underlying graph is isomorphic to G, where G is a simple graph. In the paper, we concentrate on the problem: How large the value of ∂q+(Gσ) could be among all oriented graphs in G(G)? Using majorization, we prove that Kn1,…,nk→ is the unique extremal graph which attains the maximum outdegree power ∂q+(Gσ) over all oriented graphs in G(Kn1,…,nk) for q>ln(n−n1+1)ln(1+1n−n1−1). Further, we present several results about the extrema of ∂q+(Gσ) over all complete k-partite oriented graphs.

Keywords: Outdegree power; Majorization; Oriented graphs (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S009630032200488X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:433:y:2022:i:c:s009630032200488x

DOI: 10.1016/j.amc.2022.127414

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().