Kings and serfs in oriented graphs

S. Pirzada, Nisarg ShahMathematica 2008 · DOI

Abstract In this paper, we extend the concept of kings and serfs in tournaments to that of weak kings and weak serfs in oriented graphs. We obtain various results on the existence of weak kings (weak serfs) in oriented graphs, and show the existence of n-oriented graphs containing exactly k weak kings (weak serfs), 1 ≤ k ≤ n. Also, we give the existence of n-oriented graphs containing exactly k weak kings and exactly s weak serfs such that b weak kings from k are also weak serfs.

Introduction

In classical graph theory, a tournament is a directed graph where every pair of distinct vertices is connected by exactly one directed edge. Within these structures, a king is defined as a vertex that can reach every other vertex in at most two steps. Conversely, a serf is a vertex that can be reached from every other vertex in at most two steps.

However, many real-world networks are not complete; they are better modeled as oriented graphs, where some pairs of vertices may have no edge between them. In such graphs, the traditional definitions of kings and serfs often fail to apply. This research addresses this gap by introducing the concepts of weak kings and weak serfs, where "missing" edges are accounted for in the reachability criteria, allowing for a broader study of dominance and submission in incomplete networks.

Methodology

This study utilizes formal logic and constructive graph theory to establish the properties of weak kings and serfs. Key methodological components include:

  • Scoring System: The authors implement a scoring mechanism where a vertex receives 2 points for every outgoing edge (a "win") and 1 point for every missing edge (representing a "tie" or non-connection).
  • Constructive Proofs: To demonstrate the existence of graphs with specific properties (e.g., exactly $k$ weak kings), the authors provide explicit architectural definitions for the required edge connections.
  • Proof by Contradiction: This technique is used to validate fundamental properties, such as the relationship between maximum scores and the status of a vertex as a weak king.

Key Insights and Theoretical Results

The Maximum Score Principle

In standard tournament theory, the vertex with the highest score is always a king. The authors prove a parallel principle for oriented graphs: the vertex with the maximum score (wins plus ties) is always a weak king. However, they clarify that such a vertex is not necessarily a strict king in the traditional sense.

The "No Transmitter" Rule

A "transmitter" is a vertex with an in-degree of zero. The research proves that any oriented graph lacking a transmitter is guaranteed to contain at least three weak kings, providing a lower bound for dominance in these structures.

Flexibility of Oriented Graphs

Unlike tournaments, which have strict mathematical restrictions on the number of kings they can contain (for instance, a tournament cannot have exactly two kings), oriented graphs are highly flexible. The authors demonstrate that for any valid number of vertices $n$ and any $k$ where $1 \le k \le n$, one can construct an $n$-oriented graph containing exactly $k$ weak kings.

Overlap of Dominance and Submission

The paper explores $(n, k, s, b)$-oriented graphs, which feature $n$ vertices, $k$ weak kings, $s$ weak serfs, and $b$ vertices that function as both. The authors prove that while it is impossible for all weak serfs to be weak kings if $n > k \ge s > 0$, nearly any other configuration of overlap can be mathematically constructed.

Formal Theorems

  • Theorem 2.4: Establishes that for all integers $n \ge k \ge 1$, there exists an $n$-oriented graph with exactly $k$ weak kings.
  • Theorem 2.7: Provides the construction for $(n, k, s, b)$-oriented graphs under the conditions $n \ge k \ge s > b \ge 0$ and $n \ge k + s - b$.
  • Theorem 2.8: Demonstrates that any $n$-oriented graph without a transmitter can be embedded into a larger graph such that the original vertices constitute the exact set of weak kings for the new structure.

Conclusion and Future Directions

While this paper successfully proves the existence of oriented graphs with specific numbers of weak kings and serfs, it leaves open the challenge of defining the necessary and sufficient conditions for an arbitrary $n$-oriented graph to contain exactly $k$ weak kings. Future research may also explore the computational complexity of identifying these vertices in large-scale empirical networks, such as social or biological systems, where incomplete connectivity is the norm.

Summary updated

Abstract

Abstract In this paper, we extend the concept of kings and serfs in tournaments to that of weak kings and weak serfs in oriented graphs. We obtain various results on the existence of weak kings (weak serfs) in oriented graphs, and show the existence of n-oriented graphs containing exactly k weak kings (weak serfs), 1 ≤ k ≤ n. Also, we give the existence of n-oriented graphs containing exactly k weak kings and exactly s weak serfs such that b weak kings from k are also weak serfs.
BibTeX
@inproceedings{pirzada2008kings,
  author = {S. Pirzada and Nisarg Shah},
  title = {{Kings and serfs in oriented graphs}},
  booktitle = {Mathematica},
  year = {2008},
  doi = {10.2478/s12175-008-0073-4},
}
Figure