In graph theory, the center function identifies a set of vertices in a connected graph G that minimizes the maximum distance from any other vertex. We examine the behavior of the center function on connected graphs through a set of axioms. While universal axioms apply to all connected graphs, they cannot fully characterize certain graphs. To address this limitation, non-universal axioms for specific graph classes were introduced. This study is focused on establishing an axiomatic characterization of the center function on fan graphs by utilizing a combination of universal and non-universal axioms.
Consensus is a process that serves as a cornerstone for collective decision-making. While traditional decision-making methods may prioritize majority rule or hierarchical authority, the consensus method fosters an inclusive environment where all voices are valued and considered. The study of consensus problems has garnered significant attention due to its broad applicability across various domains, such as decision theory, economics, social choice, and network analysis, see [6], [22], [8], [11]. Consensus problems often overlap with location problems, as both involve identifying an optimal point of agreement.
Through axiomatic characterization, researchers aim to define location functions based on a precise set of axioms. In many instances, the properties of a location function can be succinctly captured through an axiomatic framework. Axiomatic characterization seeks to define functions by a precise set of axioms, which describe their behaviour under various conditions. This approach provides a systematic way to understand the nature of such functions. Functions that exhibit well-ordered and intuitive behaviours can often be described by simple and elegant axioms. In contrast, functions with irregular or complex behaviours may require more intricate or less intuitive axioms to characterize their properties fully.
The idea of axiomatic characterization has its roots in the work of Kenneth Arrow [1], who pioneered the study of consensus functions in social choice theory. Arrow’s seminal work laid the groundwork for the systematic analysis of functions based on their axiomatic properties. Following this, the axiomatic characterization of location functions was first explored by Holzman [10], who studied the mean function on tree networks. Holzman’s work provided a crucial step in connecting axiomatic principles to specific mathematical structures such as graphs and networks. Building on Holzman’s foundation, Vohra extended the study to median functions on tree networks [21].
In the discrete domain, McMorris, Mulder, and Roberts further contributed by characterizing the median function on cube-free median graphs [16]. Their work highlighted the versatility of axiomatic methods in discrete settings, opening new avenues for research in combinatorial optimization. Later, the mean, median, and center functions were rigorously axiomatized, providing a mathematical framework for understanding how these functions serve as tools for achieving consensus in various contexts. For deatils see [2], [15], [14], [19], [17].
In this paper, we consider the center functions. Universal axioms are those axioms satisfied by a location function on every connected graph. For the median function, universal axioms encompass Anonymity \((A)\), Betweenness \((B)\), and Consistency \((C)\). In contrast, Population Invariance \((PI)\), Middleness \((M)\), Pre-Consistency (Pre-C), Quasi-Consistency \((QC)\), and Gatedness \((G)\) are recognized as universal axioms for the center function [3]. The center function on all trees with diameter at most 5, graphs with a dominating vertex and paths can be axiomatically characterized using these universal axioms [3]. However, using the known universal axioms, the center function cannot be characterized across all graph classes. Non-universal axioms tailored to specific graph classes have been formulated to address this. Combining these non-universal axioms with the universal axioms, the center function on graph classes like block graphs, cocktail party graphs, and complete bipartite graphs has been axiomatically characterized [5]. This study aims to unveil an axiomatic characterization of the center function on fan graphs.
Throughout this paper, we consider \(G = (V(G), E(G))\) to be an undirected, simple, connected, finite graph with vertex set \(V(G)\) and edge set \(E(G)\). For \(u\), \(v\) in \(V\), the least length of a \(u,v\)– path is called the distance from \(u\) to \(v\), and is denoted by \(d(u, v)\). The diameter of a graph \(G\) denoted by \(diam(G)\) is \(\max\{ d(u, v) : u, v \in V(G)\}\). For vertices \(u\) and \(v\) of a graph \(G\), \(u,v\)-geodesic is the shortest path joining \(u\) and \(v\). The interval \(I_G(u, v)\) between \(u\) and \(v\) in \(G\) consists of all vertices in \(u,v\)-geodesics joining \(u\) and \(v\), see [4]. A vertex \(x\) in \(G\) is called a dominating vertex if \(d(v, x) \leq 1, \forall v \in V\), see [20].
For any positive integer \(k\), a profile of length \(k\) is a non-empty sequence \(\mu= (v_1, v_2, \ldots, v_k)\) of vertices of \(V\). Vertices may be repeated in a profile. The carrier set of \(\mu\), denoted by \(\{ \mu \}\), consists of all distinct vertices in the profile \(\mu\). The number of elements in \(\{\mu \}\) is denoted by \(|\{\mu\}|\). Let \(\mu_1 = (u_1, u_2, \ldots, u_n )\) and \(\mu_2 = (v_1, v_2, \ldots, v_m)\) be any two profiles of length \(n\) and \(m\) respectively. The concatenation of \(\mu_1\) and \(\mu_2\) denoted by \(\mu_1 \mu_2\) is the profile \((u_1, u_2, \ldots, u_n, v_1, v_2, \ldots, v_m )\) of length \(n+m\). A profile \(\mu= (r_1, r_2, \ldots, r_k)\) is caled a single-occurrence profile where each \(r_i, 1\leq i\leq k\), is distinct. Further details can be found in [13].
Let \(V^*\) be the set of all profiles of finite length. A consensus function on a graph \(G\) with vertex set \(V\), defined in [18], is a function \(C:V^* \to 2^V-\emptyset\), where \(2^V\) denote the set of all subsets of \(V\). \(C((v_1, v_2, \ldots, v_n))\) is usually written as \(C(v_1, v_2, \ldots, v_n)\) where \((v_1, v_2, \ldots, v_n)\) is any profile. For any profile \(\mu\) and vertex \(u\) of \(G\), maximum distance from \(u\) to \(\mu = (v_1, v_2, \ldots, v_n)\) is defined by \(R(u, \mu)= \text{max}\{d(u, v_i) \; |\; 1\leq i\leq n\}\). The center function, denoted by Cen is a consensus function defined on \(G\), which gives the set of vertices that minimize the maximum distance to profile \(\mu\) as output for any input \(\mu\). For details of the center function, see [12].
The concept of gates was introduced by Goldman Witzgal, [9]. Let \(U\) be a subset of \(V\). A gate for a vertex \(v\) in \(V\) is a vertex \(x\) in \(U\) such that \(x\) lies in \(I(v, u)\) for any \(u\) in \(U\). That is, \(x\) serves as a gate in the set \(U\) that is closest to \(v\). Every vertex in \(U\) is its own gate. A subset \(U\) of \(V\) is known as gated if every vertex \(v \in V\) has a gate in \(U\). The gated closure of \(U\), denoted by \(Gat[U]\), is defined as the smallest gated set containing \(U\). For more properties of gated sets, see [7].
Universal axioms are those axioms that the center function satisfies on every connected graph, whereas non-universal axioms are those that the center function satisfies but only on certain graph classes. For a detailed study of universal axioms for \(Cen\), refer Changat et al. [3]. On graphs with dominating vertices, paths and trees \(T\) with \(diam(T) \leq 5\), center function can be characterized using universal axioms [3]. Below are the known universal axioms fulfilled by the center function studied in [3].
Population Invariance \((PI)\): Let \(\mu\) and \(\delta\) be two profiles with \(\{\mu\} = \{\delta \}\), then \(C(\mu)=C(\delta)\). This implies that the output solely relies on the vertices themselves without considering their multiplicities or positions within the profile.
Let \(P=u_0u_1\ldots u_{2 \ell}\) be a path of even length \(2 \ell\). The middle of path \(P\) consists of the vertex \(u_\ell\). If \(P=u_0u_1\ldots u_{2 \ell+1}\) be a path of odd length \(2 \ell+1\), middle of \(P\) consists of two vertices \(u_\ell\, \text{and} \, u_{\ell+1}\). Let \(u\) and \(v\) be any two vertices of graph \(G\). Now the middle between \(u\) and \(v\), denoted by \(Mid(u, v)\), is defined as: \(Mid(u,v)\) consists of middles of \(u,v\)-geodesics if \(d(u, v)\) is even, \(Mid(u, v)\) consists of middles of \(u, v\)– geodesics and middles of \(u, v\)-paths of length \(d(u, v)+1\) if \(d(u,v)\) is odd.
Middleness \((M)\): For any \(u, v \in V\), \(C(u,v)= Mid(u,v)\). Using middleness, outputs for all profiles of length two can be determined.
Faithfulness \((F)\): \(C(v)=\{v\}\), for all \(v \in V\).
Pre-Consistency (Pre-C): Let \(\mu\) and \(\delta\) be profiles with \(C(\mu) \cap C(\delta) \neq \emptyset\), then \(C(\mu)\cap C(\delta) \subseteq C(\mu \delta) \subseteq C(\mu)\cup C(\delta)\).
Quasiconsistency \((QC)\): Let \(\mu\) and \(\delta\) be profiles with \(C(\mu)=C(\delta)\), then \(C(\mu \delta)=C(\mu)\). Quasiconsistency follows from (Pre-C).
The characterization theorem for center function on graphs with a dominating vertex was given by Changat et al. [3] as follows.
Theorem 2.1 (Theorem 10 of [3]) Let \(G\) be a graph with dominating vertex \(a\), and let \(L\) be a consensus function defined on \(G\). Then \(L=Cen\) if and only if \(L\) satisfies \((PI), (M)\) and (Pre-C).
While the preceding list outlines known universal axioms for center functions, it should not be considered definitive. The possibility of additional yet unidentified universal axioms, remains as an open problem.
The following are the non-universal axioms used in [5] to characterize the center function on block graphs, cocktail party graphs and complete bipartite graphs. A detailed description of the non-universal axioms and characterization of \(Cen\) on the above graphs using both universal and non-universal axioms can be seen in [5].
Redundancy \((R)\): Let \(\mu = (x_1, x_2, \ldots, x_k)\) be any profile. If \(x_i \in Gat(\mu-x_i), \, \text{then} \, C(\mu-x_i)=C(\mu)\).
Inconclusiveness \((Inc)\): For a profile \(\mu = (x_1, x_2, \ldots, x_k)\), if \(\cap_{i=1}^{k} C(\mu-x_i)=\emptyset\), then \(C(\mu)=Gat(\mu)\).
Recursive Consistency \((RC)\): For a single-occurrence profile \(\mu = (x_1, x_2, \ldots, x_k)\) with \(k\geq 3\), if \(\cap_{i=1}^{k} C(\mu-x_i) \neq \emptyset\), then \(C(\mu)=\cap_{i=1}^{k}C(\mu-x_i)\).
Fullness \((Full)\): \(C(V)=V\).
A fan graph, denoted by \(F_{m,n}\), is defined as the join of the complement of the complete graph, \(\overline{K_{m}}\) and path on \(n\) vertices \(P_n\). Thus, \(F_{m,n} = \overline{K_{m}} + P_n\). Fan graph \(F_{m,n}\), contains \(m+n\) vertices and \(mn+n-1\) edges. Let the vertex set of fan graph be denoted by \(V(F_{m,n}) = W \cup Z\), where \(W=\{w_1, w_2, \ldots, w_m \}\) denote the vertices of \(\overline{K_{m}}\) and \(Z=\{z_1, z_2, \ldots, z_n \}\) denote the vertices of \(P_n\). The distance between two vertices say \(z_i\) and \(z_j\) of \(F_{m,n}\) in path \(P_n\) is denoted by \(d_{P_n}(z_i, z_j)\). Fan graph \(F_{3,4}\) is given below in Figure 1.
A vertex \(u\) in a graph \(G\) is said to be dominating vertex to a profile \(\pi = (v_1, v_2, \ldots, v_n)\) if \(d(u, v_i)\leq 1\) for \(1 \leq i \leq n\). If a profile has a dominating vertex, then that profile is called a dominating profile and a profile which does not have a dominating vertex is called a non-dominating profile. The set of all vertices in \(Z\) that are dominating to a profile \(\pi\) is called \(\pi\)-dominators, denoted by \(D_{\pi}\). For example consider \(F_{3,4}\). Then \(d_{P_4}(z_1, z_3) = 2\) and \(d_{P_4}(z_1, z_4) = 3\). Let \(\pi = (w_1, w_3, z_1, z_3)\). Then, \(D_{\pi} = D_{(z_1, z_3)} = \{z_2 \}\). Let \(\rho = \{w_1, w_2, z_2 \}\). Then, \(D_{\rho} = D_{z_2} = \{z_1, z_2, z_3 \}\). If \(| \{\pi \} \cap Z | = 1\), then \(D_{\pi} \neq \emptyset\). Also for \(|\{\pi \} \cap Z| \geq 4, D_{\pi} = \emptyset\).
Profiles on \(F_{m,n}\) can be classified as follows:
1. \(|\{\pi \}| = 1\). This profile is called \(T_1\) profile.
2. \(|\{\pi \}| \geq 2\) and \(\{\pi \} \subseteq W\). This profile is called \(T_2\) profile.
3. \(|\{\pi \}| \geq 2\) and \(\{\pi \} \subseteq Z\). This profile is called \(T_3\) profile.
4. \(|\{\pi \} \cap W| = 1\) and \(|\{\pi \} \cap Z| \geq 1\). This profile is called \(T_{4a}\) profile.
5. \(|\{\pi \} \cap W| \geq 2\), \(|\{\pi \} \cap Z| \geq 1\) and \(D_{\pi} \neq \emptyset\). This profile is called \(T_{4b}\) profile. In this type \(|\{\pi \} \cap Z| \leq 3\).
6. \(|\{\pi \} \cap W| \geq 2\), \(|\{\pi \} \cap Z| \geq 2\) and \(D_{\pi} = \emptyset\). This profile is called \(T_{4c}\) profile.
From this classification of profiles, profiles \(T_1, T_2, T_3, T_{4a}\) and \(T_{4b}\) are identified as dominating profiles, while \(T_{4c}\) is a non-dominating profile. Next, we will determine the center of the profiles defined on fan graph \(F_{m,n}\).
Lemma 3.1. Let \(\pi\) be a profile defined on fan graph \(F_{m,n}\) such that \(|\{\pi \}| \geq 2\) and \(\{\pi \} \subseteq W\). Then, \(Cen(\pi) = Z\).
Proof. Since \(|\{\pi \}| \geq 2\) and \(\{\pi \} \subseteq W\), \(R(w, \pi) = 2\), for every \(w \in W\). But for each \(z \in Z\), \(R(z, \pi) = 1\). Hence, \(Cen(\pi) = Z\). ◻
Lemma 3.2. Let \(\pi\) be a profile defined on fan graph \(F_{m,n}\) such that \(|\{\pi \}| \geq 2\) and \(\{\pi \} \subseteq Z\). Then, \(Cen(\pi) = W \cup D_{\pi}\). But if \(|\{\pi \}| \geq 4\) and \(\{\pi \} \subseteq Z\), then \(Cen(\pi) = W\).
Proof. For each \(w \in W\), \(R(w, \pi) =1\). Also for each \(z \in D_{\pi}\), \(R(z, \pi) =1\). But for each \(z \in Z- D_{\pi}\), \(R(z, \pi) =2\). Hence, \(Cen(\pi) = W \cup D_{\pi}\). If \(|\{\pi \}| \geq 4\), then \(D_{\pi} = \emptyset\). Hence, \(Cen(\pi) = W\). ◻
Lemma 3.3. Let \(\pi\) be a profile defined on fan graph \(F_{m,n}\) such that \(|\{\pi \} \cap W| =1\) and \(|\{\pi \} \cap Z| \geq 1\). Then, \(Cen(\pi) = \{w'\} \cup D_{\pi}\), where \(\{\pi \} \cap W =\{w'\}\).
Proof. Here \(R(w',\pi) = 1\). For each \(w \in W-w'\), \(R(w, \pi)=2\). Also for each \(z \in D_{\pi}\), \(R(z, \pi) =1\) and for each \(z \in Z- D_{\pi}, R(z, \pi) =2\). Hence, \(Cen(\pi) = \{w'\} \cup D_{\pi}\). ◻
Lemma 3.4. For any profile \(\pi\) defined on fan graph \(F_{m,n}\), with \(|\{\pi \} \cap W| \geq 2\), \(|\{\pi \} \cap Z| \geq 1\) and \(D_{\pi} \neq \emptyset\), \(Cen(\pi) = D_{\pi}\).
Proof. Since \(|\{\pi \} \cap W| \geq 2\), \(R(w, \pi)=2\) for each \(w \in W\). Also for each \(z \in D_{\pi}, R(z, \pi) =1\) and \(z \in Z-D_{\pi}, R(z, \pi) =2\). Hence, \(Cen(\pi) = D_{\pi}\). ◻
Lemma 3.5. For any profile \(\pi\) defined on fan graph \(F_{m,n}\), with \(|\{\pi \} \cap W| \geq 2\), \(|\{\pi \} \cap Z| \geq 2\) and \(D_{\pi} = \emptyset\), \(Cen(\pi) = V(F_{m,n})\).
Proof. Since \(|\{\pi \} \cap W| \geq 2\), \(R(w, \pi)=2\) for each \(w \in W\). Also since \(|\{\pi \} \cap Z| \geq 2\) and \(D_{\pi} = \emptyset\), \(R(z, \pi) =2\), for every \(z \in Z\). Hence, \(Cen(\pi) = W \cup Z = V(F_{m,n})\). ◻
In this section first we show that for any consensus function \(C\) defined on fan graph satisfying the universal axioms, \((PI), (M)\) and (Pre-C), \(C(\pi) = Cen(\pi)\), whenever \(\pi\) is a dominating profile.
Theorem 4.1. Let \(C\) be a consensus function defined on fan graph \(F_{m,n}\). If \(C\) satisfy \((PI), (M)\) and (Pre-C), then \(C(\pi) = Cen(\pi)\), for any \(T_2\) profile and for any \(T_3\) profile.
Proof. Let \(C\) be a consensus function satisfying \((PI), (M)\) and (Pre-C), defined on fan graph \(F_{m,n}\). By \((PI)\), we need to consider only single-occurrence profiles. Let \(\pi = (v_1, v_2, \ldots, v_n)\) be a single-occurrence profile.
Let \(\pi\) be any profile of type \(T_2\). Therefore \(|\{\pi \}|\geq 2\) and \(\{\pi \} \subseteq W\). By \((M)\), \(C(v_1, v_i) = Z\), where \(2\leq i \leq n\). Hence, by \((PI)\) and (Pre-C), \(C(v_1, v_2, \ldots, v_n) =Z = Cen(\pi)\).
Let \(\pi = (v_1, v_2, \ldots, v_n)\) be any profile of type \(T_3\). Therefore \(|\{\pi \}|\geq 2\) and \(\{\pi \} \subseteq Z\). We prove that \(C=Cen\) by applying mathematical induction on \(n\). By \((PI)\) and \((M)\), \(C(\pi) =Cen(\pi)\), for any profile \(\pi\) with \(|\{\pi \}| \leq 2\). First, we prove that the result is true for \(n=3\). Let \(\pi = (v_1, v_2, v_3)\).
Case 1. Let \(D_{\pi} \neq \emptyset\). Then, there exists a vertex, say \(v \in Z\) dominating to \(\pi\). Then, \(v\) must belong to \(\{\pi \}\). Without loss of generality, assume that \(v=v_1\). Then, \(v_1\) is adjacent to \(v_2\) and \(v_3\). By \((M)\), we have, \(C(v_1, v_2) = W \cup \{v_1, v_2 \}, C(v_1, v_3) = W \cup \{v_1, v_3 \}, C(v_2, v_3) = W \cup \{v_1\}\). By \((PI)\) and (Pre-C), we have \[\ W \cup \{v_1 \} \subseteq C(v_1, v_2, v_3) \subseteq W \cup \{v_1, v_2, v_3 \},\label{e1}\tag{1}\] \[W \cup \{v_1 \} \subseteq C(v_1, v_2, v_3) \subseteq W \cup \{v_1, v_3 \},\label{e2}\tag{2}\] \[W \cup \{v_1 \} \subseteq C(v_1, v_2, v_3) \subseteq W \cup \{v_1, v_2\}.\label{e3} \tag{3}\]
From (2), \(v_2 \notin C(\pi)\) and from (3), \(v_3 \notin C(\pi)\). Hence, from (1), \(C(v_1, v_2, v_3) = W \cup \{v_1\} = W \cup D_{\pi} = Cen(\pi)\).
Case 2. Let \(D_{\pi} = \emptyset\). Then, there exist at least two vertices \(v_i\) and \(v_j\) such that \(d_{P_n}(v_i, v_j) \geq 3\). Without loss of generality, assume that \(d_{P_n}(v_1, v_2) \geq 3\). By \((M)\), \[\begin{aligned} \label{e4} C(v_1, v_2) = W, C(v_1,v_3) = W \cup D_{(v_1, v_3)}, C(v_2, v_3) = W \cup D_{(v_2, v_3)}. \end{aligned} \tag{4}\]
Then, \(D_{(v_1, v_3)} \cap D_{(v_2, v_3)} = \emptyset\). For, \(v_k \in D_{(v_1, v_3)} \cap D_{(v_2, v_3)} \Rightarrow v_k\) is adjacent to \(v_1\) and \(v_3\) and \(v_k\) is adjacent to \(v_2\) and \(v_3\) \(\Rightarrow\) \(v_k\) is adjacent to \(v_1, v_2\) and \(v_3\). This is a contradiction since \(D_(v_1, v_2, v_3) = D_{\pi} = \emptyset\).
Hence, from (4), by \((PI)\) and (Pre-C), \[\begin{aligned} W \subseteq C(v_1, v_2, v_3) \subseteq W \cup D_{(v_1, v_3)},\\ W \subseteq C(v_1, v_2, v_3) \subseteq W \cup D_{(v_2, v_3)}. \end{aligned}\]
Since \(D_{(v_1, v_3)} \cap D_{(v_2, v_3)} = \emptyset\), \(C(v_1, v_2, v_3) = W = Cen(v_1, v_2, v_3)\).
Hence, the result is true for \(n=3\). Suppose that the result is true for \(n=k-1\). Let \(\pi = (v_1, v_2, \ldots, v_k)\), where \(k \geq 4\). In this case \(D_{\pi} = \emptyset\). So there exist two vertices say, \(v_1\) and \(v_2\) such that \(d(v_1, v_2) \geq 3\). By induction hypothesis, \(C(v_1, v_2, \ldots, v_{k-1}) = W = C(v_1, v_2, v_4, \ldots, v_k)\). Hence, by \((PI)\) and (Pre-C), \(C(v_1, v_2, \ldots, v_k) = W = Cen(v_1, v_2, \ldots, v_k)\). ◻
Theorem 4.2. Let \(C\) be a consensus function defined on fan graph \(F_{m,n}\). If \(C\) satisfies \((PI), (M)\) and (Pre-C), then \(C(\pi) =Cen(\pi)\), for any \(T_{4a}\) profile.
Proof. Since \(\pi\) is a \(T_{4a}\) profile, \(|\{ \pi\} \cap W|=1\) and \(|\{\pi \} \cap Z| \geq 1\). By \((PI)\), we need to consider only single-occurrence profiles. Let \(\pi = (v_1, v_2, \ldots, v_n)\) be a single-occurrence profile. By \((PI)\) and \((M)\), \(C(\pi) = Cen(\pi)\), for all profiles with \(|\{\pi \}| \leq 2\).
Case 1. Let \(D_{\pi} \neq \emptyset\). Then, \(|\{\pi \} \cap Z| \leq 3\).
Subcase 1.1. Let \(|\{\pi \} \cap Z | = 1\). Then, \(|\{\pi \}| =2\). So by \((PI)\) and \((M)\), \(C(\pi) = Cen(\pi)\).
Subcase 1.2. Let \(|\{\pi \} \cap Z | =2\). Let \(\pi =(v_1, v_2, v_3)\). Without loss of generality, assume that \(\{\pi \} \cap W = \{v_1\}\). Then, \(v_2, v_3 \in Z\). By \((M)\), \[\begin{aligned} C(v_1, v_2) = \{v_1\} \cup D_{v_2}, C(v_1, v_3) = \{v_1\} \cup D_{v_3}, C(v_2, v_3) = W \cup D_{(v_2, v_3)}, \end{aligned}\]
Since \(D_{v_2} \cap D_{v_3} = D_{(v_2, v_3)}\), by \((PI)\) and (Pre-C), \[ \{v_1\}\cup D_{(v_2, v_3)} \subseteq C(v_1, v_2, v_3) \subseteq W \cup D_{v_2}, \label{e5}\tag{5}\] \[\{v_1\} \cup D_{(v_2, v_3)} \subseteq C(v_1, v_2, v_3) \subseteq W \cup D_{v_3}, \label{e6}\tag{6}\] \[\{v_1\} \cup D_{(v_2, v_3)} \subseteq C(v_1, v_2, v_3) \subseteq \{v_1\} \cup D_{v_2} \cup D_{v_3}. \label{e7} \tag{7}\]
Now \(\eqref{e5} \Rightarrow (Z-D_{v_2}) \cap C(\pi) = \emptyset\), \(\eqref{e6} \Rightarrow (Z- D_{v_3}) \cap C(\pi) = \emptyset\) and \(\eqref{e7} \Rightarrow (W-\{v_1\}) \cap C(\pi) = \emptyset\).
Hence, \[\{v_1\} \cup D_{(v_2, v_3)} \subseteq C(v_1, v_2, v_3) \subseteq \{v_1\} \cup D_{(v_2, v_3)}.\]
Thus, \(C(\pi) = \{v_1\} \cup D_{(v_2, v_3)} = \{v_1\} \cup D_{\pi} = Cen(\pi)\).
Subcase 1.3. Let \(|\{\pi \} \cap Z | =3\). Let \(\pi = (v_1, v_2, v_3, v_4)\), where \(\{\pi \} \cap W = \{v_1\}\) and \(\{\pi \} \cap Z = \{v_2, v_3, v_4\}\). Since \(D_{\pi} \neq \emptyset\), \(v_2, v_3\) and \(v_4\) induce a path \(P = v_2v_3v_4\). By Subcase 1.2 and \((PI)\), \(C(v_1, v_2, v_3) = \{v_1\} \cup D_{(v_2, v_3)} = \{v_1, v_2, v_3\}\), \(C(v_1, v_2, v_4) = \{v_1\} \cup D_{(v_2, v_4)} = \{v_1, v_3\}\) and \(C(v_1, v_3, v_4) = \{v_1\} \cup D_{(v_3, v_4)} = \{v_1, v_3, v_4\}\). Hence, by \((PI)\) and (Pre-C), \[\{v_1, v_3\} \subseteq C(v_1, v_2, v_3, v_4) \subseteq \{v_1, v_2, v_3\}, \label{e8}\tag{8}\] \[\{v_1, v_3\} \subseteq C(v_1, v_2, v_3, v_4) \subseteq \{v_1, v_2, v_3, v_4 \}, \label{e9}\tag{9}\] \[\{v_1, v_3\} \subseteq C(v_1, v_2, v_3, v_4) \subseteq \{v_1, v_3, v_4\}. \label{e10} \tag{10}\]
(8) \(\Rightarrow v_4 \notin C(v_1, v_2, v_3, v_4)\) and (10) \(\Rightarrow v_2 \notin C(v_1, v_2, v_3, v_4)\). Hence, \(C(v_1, v_2, v_3, v_4) = \{v_1, v_3 \} = Cen(v_1, v_2, v_3, v_4)\).
Case 2. Let \(D_{\pi} = \emptyset\). We prove that \(C=Cen\) by applying mathematical induction on \(|\{\pi \}|= n\). First, we prove that the result is true for \(n=3\). Let \(\pi =(v_1, v_2, v_3)\). Without loss of generality, assume that \(\{\pi \} \cap W = \{v_1\}\) and \(\{\pi \} \cap Z = \{v_2, v_3 \}\). Then, since \(D_{\pi} = \emptyset\), \(D_{(v_2, v_3)} = \emptyset\). By \((M)\), \[C(v_1, v_2) = \{v_1\} \cup D_{v_2}, C(v_1, v_3) = \{v_1\} \cup D_{v_3}, C(v_2, v_3) = W\] By \((PI)\) and (Pre-C), we have \[\{v_1\} \cup D_{(v_2, v_3)} \subseteq C(v_1, v_2, v_3) \subseteq \{v_1\} \cup D_{v_2} \cup D_{v_3}, \label{e11}\tag{11}\] \[\{v_1\} \subseteq C(v_1, v_2, v_3) \subseteq W \cup D_{v_3}, \label{e12} \tag{12}\] \[\{v_1\} \subseteq C(v_1, v_2, v_3) \subseteq W \cup D_{v_2}. \label{e13} \tag{13}\]
Now \(\eqref{e12} \Rightarrow (Z-D_{v_3}) \cap C(v_1, v_2,v_3) = \emptyset\), \(\eqref{e13} \Rightarrow (Z-D_{v_2}) \cap C(v_1, v_2,v_3) = \emptyset\). Hence, \(( Z-D_{(v_2,v_3)}) \cap C(v_1, v_2,v_3) = \emptyset\). Since \(D_{(v_2,v_3)} = \emptyset, Z \cap C(v_1, v_2,v_3)= \emptyset\). \(\eqref{e11} \Rightarrow (W-v_1) \cap C(v_1, v_2, v_3) = \emptyset\). Thus, \(\{v_1\} \subseteq C(v_1, v_2, v_3) \subseteq \{v_1\}\). Hence, \(C(\pi) = \{v_1\} = Cen(\pi)\). Assume that the result is true for \(n=k-1\). We will prove that the result is true for \(n=k\). Let \(\pi = (v_1, v_2, \ldots, v_k)\) be a single-occurrence profile with \(k \geq 4\). Without loss of generality assume that \(v_1 \in W\). Since \(D_{z_{\pi}} = \emptyset\), there exists two vertices say \(v_2\) and \(v_3\), such that \(d(v_2, v_3) \geq 3\). By induction hypothesis, \(C(v_1, v_2,v_3, v_4, \ldots, v_{k-1}) = C(v_1, v_2,v_3,v_5, \ldots, v_k) = \{v_1\}\). By \((PI)\) and (Pre-C), \(C(v_1, v_2, \ldots, v_k) = \{v_1\} = Cen(v_1, v_2, \ldots, v_k)\). Hence, \(C=Cen\). ◻
Theorem 4.3. Let \(C\) be a consensus function satisfying \((PI), (M)\) and (Pre-C) defined on fan graph \(F_{m,n}\). Then, for any \(T_{4b}\) profile, \(C(\pi) = Cen(\pi)\).
Proof. By \((PI)\), we need to consider only single-occurrence profile. Let \(\pi = (v_1, v_2, \ldots, v_n)\) be a single-occurrence profiles. In this case for any profile \(\pi\), \(|\{\pi \}| \geq 3\). We consider the following three cases.
Case 1. Let \(|\{\pi \} \cap Z| =1\). Let \(\pi = (v_1, v_2, \ldots, v_n)\). The proof is obtained by applying mathematical induction on \(n\). First, we prove that the result is true for \(n=3\). Let \(\pi = (v_1, v_2, v_3)\), with \(\{\pi \} \cap Z = \{v_1\}\) and \(\{\pi \} \cap W = \{v_2, v_3 \}\). By \((M)\), \(C(v_1, v_2) = \{v_2\} \cup D_{v_1}\), \(C(v_1, v_3) = \{v_3\} \cup D_{v_1}\) and \(C(v_2, v_3) = Z\). By \((PI)\) and (Pre-C), \[ D_{v_1} \subseteq C(\pi) \subseteq \{v_2, v_3\} \cup D_{v_1}, \label{e14} \tag{14}\] \[D_{v_1} \subseteq C(\pi) \subseteq \{v_3\} \cup Z , \label{e15}\tag{15}\] \[D_{v_1} \subseteq C(\pi) \subseteq \{v_2\} \cup Z. \label{e16} \tag{16}\]
(14) \(\Rightarrow (Z-D_{v_1}) \cap C(\pi) = \emptyset\), (15) \(\Rightarrow v_2 \notin C(\pi)\) and (16) \(\Rightarrow v_3 \notin C(\pi)\). Hence, \(D_{v_1} \subseteq C(\pi) \subseteq D_{v_1}\). Thus, \(C(\pi) = D_{v_1} = Cen(\pi)\). Assume that the result is true for all profiles \(\pi\) with \(|\{\pi \}| < k\). Let \(\pi = (v_1, v_2, \ldots, v_k)\). Without loss of generality, let \(\{\pi \} \cap Z = \{v_1\}\) and \(\{\pi \} \cap W = \{v_2, v_3, \ldots, v_k\}\). By induction hypothesis, \(C(v_1, v_2, \ldots, v_{k-1}) = Cen(v_1, v_2, \ldots, v_{k-1}) = D_{v_1}\) and \(C(v_1, v_3, \ldots, v_k) = Cen(v_1, v_3, \ldots, v_k) = D_{v_1}\). By \((PI)\) and (Pre-C), \(C(v_1, v_2, \ldots, v_k) = D_{v_1} = Cen(v_1, v_2, \ldots, v_k)\). Hence, \(C(\pi) =Cen(\pi)\) for all profiles \(\pi\) with \(|\{\pi \} \cap W| \geq 2\) and \(|\{\pi \} \cap Z | =1\).
Case 2. Let \(|\{\pi \} \cap Z| =2\). Let \(\pi = (v_1, v_2, \ldots, v_n)\). Without loss of generality, let \(\{\pi \} \cap Z = \{v_1, v_2\}\) and \(\{\pi\} \cap W = \{v_3, v_4, \ldots, v_n\}\). By Case 1, \(C(v_1, v_3, \ldots, v_n) = D_{v_1}\) and \(C(v_2, v_3, \ldots, v_n) =D_{v_2}\). By \((PI)\) and (Pre-C), \[\begin{aligned} \label{e17} D_{(v_1, v_2)} \subseteq C(\pi) \subseteq D_{v_1} \cup D_{v_2}. \end{aligned} \tag{17}\]
By Theorem 4.2 and Lemma 3.3, \(C(v_1, v_2, v_i) = \{v_i\} \cup D_{(v_1, v_2)}, i=3, 4, \ldots, n\). By \((PI)\) and (Pre-C), \[\begin{aligned} \label{e18} D_{(v_1, v_2)} \subseteq C(\pi) \subseteq \{v_3, v_4, \ldots, v_n\} \cup D_{(v_1, v_2)}. \end{aligned} \tag{18}\]
From (17) and (18), \(D_{(v_1, v_2)} \subseteq C(\pi) \subseteq D_{(v_1, v_2)}\). Hence, \(C(\pi) = D_{(v_1, v_2)} = Cen(\pi)\).
Case 3. Let \(|\{\pi \} \cap Z| =3\). Let \(\pi = (v_1, v_2, \ldots, v_n)\). Without loss of generality, let \(\{\pi \} \cap Z = \{v_1, v_2, v_3\}\) and \(\{\pi\} \cap W = \{v_4, v_5, \ldots, v_n\}\). Then, the subgraph induced by \(v_1, v_2\) and \(v_3\) is a path, say \(P=v_1v_2v_3\). Since \(C\) satisfies \((PI), (M)\) and (Pre-C), by Case 2,
\(C(v_1, v_2, v_4, \ldots, v_n) = D_{(v_1, v_2)} = \{v_1, v_2\}\), \(C(v_1, v_3,v_4, \dots, v_n) = D_{(v_1, v_3)} = \{v_2\}\), \(C(v_2, v_3, v_4, \ldots,\\ v_n) = D_{(v_2, v_3)} = \{v_2, v_3\}\). By \((PI)\) and (Pre-C), \[\{v_2\} \subseteq C(\pi) \subseteq \{v_1, v_2\}, \label{e19}\tag{19}\] \[\{v_2\} \subseteq C(\pi) \subseteq \{v_2, v_3\}, \label{e20}\tag{20}\] \[\{v_2\} \subseteq C(\pi) \subseteq \{v_1, v_2, v_3\}. \label{e21} \tag{21}\] From (19), (20) and (21), \(\{v_2\} \subseteq C(\pi) \subseteq \{v_2\}\). Hence, \(C(\pi) = \{v_2\} = Cen(\pi)\).
Corollary 4.4. Let \(C\) be a consensus function satisfying \((PI), (M)\) and (Pre-C) defined on fan graph \(F_{m,n}\) where \(n \leq 3\). Then, for any profile with \(|\{\pi \} \cap W| \geq 2\) and \(|\{\pi \} \cap Z | \geq 1\), \(C(\pi) = Cen(\pi)\).
Proof. Since we are considering fans \(F_{m,n}\) where \(n \leq 3\) and since \(|\{\pi \} \cap Z | \geq 1\), \(D_{\pi} \neq \emptyset\). Hence, by Theorem 4.3, \(C(\pi) =Cen(\pi)\). ◻
Corollary 4.5. Let \(C\) be a consensus function defined on fan graph \(F_{m,n}\), where \(n \leq 3\). Then, \(C = Cen\) if and only if \(C\) satisfies \((PI), (M)\) and (Pre-C).
Proof. Since fan graph \(F_{m,n}\), with \(n \leq 3\) is a graph with dominating vertex, by Theorem 1, \(C = Cen\). ◻
Thus, \(Cen\) can be characterized on all fans \(F_{m,n}\) where \(n \leq 3\) using universal axioms. However, fans \(F_{m,n}\), where \(n \geq 4\) cannot be characterized using universal axioms (PI), (M) and (Pre-C). Consider the example given below.
Example 4.6. Let \(C\) be a consensus function defined on fan graph \(F_{m,n}, n \geq 4\) as follows \[C(\pi) = \begin{cases} W & \text{if}~\pi ~\text{is a non-dominating profile,} \\ Cen(\pi) & otherwise . \end{cases}\]
The consensus function defined above satisfies \((PI), (M)\) and (Pre-C). But this function \(C\) is not the \(Cen\) function. The following proposition gives a justification for these claims.
Proposition 4.7. \(C\) satisfies \((PI), (M)\) and (Pre-C), but \(C \neq Cen\).
Proof. Let \(S= \{\pi \colon \pi ~\text{is a non-dominating profile} \} = \{\pi \colon |\{\pi \} \cap W| \geq 2, |\{\pi \} \cap Z| \geq 2\) and \(D_{\pi} = \emptyset \}\). For \(\pi \in S, C(\pi) = W\) and \(Cen(\pi) = V\). Hence, \(C \neq Cen\). By definition, \(C\) satisfies \((PI)\) and \((M)\). We will prove that \(C\) satisfies (Pre-C). Let \(\pi\) and \(\rho\) be two profiles with \(C(\pi) \cap C(\rho) \neq \emptyset\).
Case 1. Let \(\pi \in S\) and \(\rho \in S\). Then, \(\pi\rho \in S\). Hence, \(C(\pi) = C(\rho) =C(\pi\rho) =W\). Hence, (Pre-C) is satisfied.
Case 2. Let \(\pi \in S\) and \(\rho \notin S\). In this case \(\pi\rho \in S\) and \(C(\pi) = C(\pi\rho)\). Similarly if \(\pi \notin S\) and \(\rho \in S\), then \(\pi\rho \in S\) and \(C(\pi\rho) = C(\rho)\). Hence, (Pre-C) is satisfied.
Case 3. Let \(\pi \notin S, \rho \notin S\) and \(\pi\rho \notin S\). Then, \(C(\pi) = Cen(\pi), C(\rho) = Cen(\rho), C(\pi\rho) = Cen(\pi\rho)\). Hence, (Pre-C) is satisfied.
Case 4. Let \(\pi \notin S, \rho \notin S\) and \(\pi\rho \in S\). Since \(\pi\rho \in S\), \(D_{\pi\rho} = \emptyset\). We consider the following cases.
1. Let \(\pi\) is of type \(T_2\). Then, \(C(\pi) = Z\).
If \(\rho\) is of type \(T_2\), then \(\pi\rho \notin S\), which is not possible.
If \(\rho\) is of type \(T_3\), since \(\pi\rho \in S\), we must have \(D_{\rho} = \emptyset\). Then, \(C(\rho) = W\). So \(C(\pi) \cap C(\rho) = \emptyset\), which is against the condition of (Pre-C).
If \(\rho\) is of type \(T_{4a}\), since \(\pi\rho \in S\), we must have \(D_{\rho} = \emptyset\). Then, \(C(\rho) = w\), where \(w \in W\). So \(C(\pi) \cap C(\rho) = \emptyset\).
If \(\rho\) is of type \(T_{4b}\), since \(D_{\rho} \neq \emptyset\), \(\pi\rho \notin S\).
2. Let \(\pi\) is of type \(T_3\). Then, \(C(\pi) = W \cup D_{\pi}\).
If \(\rho\) is of type \(T_3\) or type \(T_{4a}\), then since \(|\{\pi \} \cap W| \leq 1\), \(\pi\rho \notin S\).
If \(\rho\) is of type \(T_{4b}\), \(C(\rho) = D_{\rho}\). Since \(\pi\rho \in S, D_{\pi} \cap D_{\rho} = D_{\pi\rho} = \emptyset\). So \(C(\pi) \cap C(\rho) =\emptyset\).
3. Let \(\pi\) is of type \(T_{4a}\).
If \(\rho\) is of type \(T_{4a}\) or type \(T_{4b}\), then \(C(\pi) \cap C(\rho) = \emptyset\).
Let \(\pi\) is of type \(T_{4b}\). If \(\rho\) is also of type \(T_{4b}\), then \(C(\pi) \cap C(\rho) = \emptyset\).
Thus, in all cases, (Pre-C) is satisfied. ◻
Thus, for characterizing \(Cen\), we need class-specific axioms. So we define the following non-universal axiom for characterizing \(Cen\) on \(F_{m,n}, n \geq 4\).
Totality (T): \(C(\pi) = V\), if \(\pi\) is a non-dominating profile.
Using the Totality \((T)\) axiom along with the universal axioms \((PI), (M)\) and (Pre-C), we will be able to characterize \(Cen\) on fan graphs \(F_{m,n}, n\geq 4\).
Theorem 4.8. Let \(C\) be a consensus function defined on fan graph \(F_{m,n}\), where \(n \geq 4\). Then, \(C = Cen\) if and only if \(C\) satisfies \((PI), (M)\), (Pre-C) and \((T)\).
Proof. Let \(C = Cen\), then by definition \(C\) satisfies \((PI), (M)\), (Pre-C) and \((T)\). Conversely, suppose that \(C\) satisfies \((PI), (M)\), (Pre-C) and \((T)\). By \((PI)\) and \((M)\), \(C(\pi) = Cen(\pi)\), for all profiles \(\pi\) with \(|\{\pi \}| \leq 2\). Then if \(\pi\) is a dominating profile, we have the following cases.
1. Let \(|\{\pi \}| \geq 2\) and \(\{\pi \} \subseteq W\). Then, by Theorem 4.1, \(C(\pi) = Cen(\pi)\).
2. Let \(|\{\pi \}| \geq 2\) and \(\{\pi \} \subseteq Z\). Then, by Theorem 4.1, \(C(\pi) = Cen(\pi)\).
3. Let \(|\{\pi \} \cap W|=1\) and \(|\{\pi \} \cap Z |\geq 1\). Then, by Theorem 4.2, \(C(\pi) = Cen(\pi)\).
4. Let \(|\{\pi \} \cap W|\geq 2\), \(|\{\pi \} \cap Z |\geq 1\) and \(D_{\pi} \neq \emptyset\). Then, by Theorem 4.3, \(C(\pi) = Cen(\pi)\).
If \(\pi\) is a non-dominating profile, then \(|\{\pi \} \cap W|\geq 2\), \(|\{\pi \} \cap Z |\geq 2\) and \(D_{\pi} = \emptyset\). Then, by \((T)\) and Lemma 3.5, \(C(\pi) = Cen(\pi)\). Thus, in all cases \(C(\pi) = Cen(\pi)\), for any profile \(\pi\). Hence, \(C = Cen\). ◻
Now, we check the independence of axioms for characterizing the center function on fan graphs. The consensus function \(C\) in Example 4.6 satisfies \((PI), (M)\), and (Pre-C), but not \((T)\). The independence of the remaining axioms is as follows:
Example 5.1 (Not (Pre-C)).Let \(C\) be a consensus function defined on \(F_{m,n}, m\geq 2\) by \[C(\pi) = \begin{cases} Cen(\pi) & $ if $ |\{\pi \}| \leq 2 ,\\ V & $ if $ |\{\pi \}| \geq 3, \end{cases}\] for any profile \(\pi\).
In the following proposition, we prove the independence of (Pre-C) using the function \(C\) defined above.
Proposition 5.2. \(C\) satisfies \((PI), (M)\) and \((T)\). But \(C\) does not satisfy (Pre-C).
Proof. By definition, \(C\) satisfies \((PI), (M)\) and \((T)\). Let \(\rho = (w_1, z_1)\) and \(\delta = (w_1,z_2)\). Then, \(C(\rho) = (w_1, z_1, z_2)\), \(C(\delta) = (w_1, z_1, z_2, z_3)\) and \(C(\pi\rho) = C(w_1, z_1, z_2) = V\). Now \(C(\pi\rho) \nsubseteq C(\pi) \cup C(\rho)\). Hence, (Pre-C) is violated. ◻
Example 5.3 (Not (M)).Let \(C\) be a consensus function defined on \(F_{m,n}\) as follows: \(C(\pi) = V,~ \text{for any profile} ~ \pi.\)
By definition, \(C\) satisfies \((PI)\), (Pre-C) and \((T)\). But \(C\) does not satisfy \((M)\), since \(C(w_1, w_2) = V\). But \(Mid(w_1, w_2) = Z\).
Example 5.4(Not (PI)).Let \(\pi = (v_1, v_2, \ldots, v_n)\) be any profile of length \(n\). Let \(C\) be the consensus function defined on \(F_{2,2}\) as follows: \[C(\pi) = \begin{cases} z_1 & $ if $ v_1=v_2=z_1, \{\pi \} =\{z_1, z_2 \},\\ Cen(\pi) & otherwise. \end{cases}\]
We prove the independence of the \((PI)\) axiom through the following proposition, using the function \(C\) defined above.
Proposition 5.5. \(C\) satisfies \((M), (T)\) and (Pre-C), but not (PI).
Proof. By definition, \(C\) satisfies \((M)\) and \((T)\). Let \(K=\{\pi = (v_1, v_2, \ldots, v_n) \colon v_1=v_2=z_1\}\) and \(\{ \pi \} = \{z_1, z_2 \}\). Let \(\pi\) and \(\rho\) be two profiles with \(C(\pi) \cap C(\rho) \neq \emptyset\). We consider the following cases:
1. Let \(\pi \in K\) and \(\rho \in K\). Then, \(\pi\rho \in K\). Then, \(C(\pi) = C(\rho) = C(\pi\rho) = \{z_1\}\).
2. Let \(\pi \notin K\) and \(\rho \notin K\). Then, if \(\pi\rho \notin K\). Hence, \(C(\pi) =Cen(\pi), C(\rho) = Cen(\rho)\) and \(C(\pi\rho) = Cen(\pi\rho)\). If \(\pi\rho \in K\), then \(\{\pi \} = \{z_1\}\) and \(\rho = (v_1, v_2, \ldots, v_k)\) with \(v_1 = z_1, v_2=z_2\) and \(\{\rho \} = \{z_1, z_2\}\). Then \(C(\pi) = \{z_1\} = C(\pi\rho)\).
3. Let \(\pi \in K\), \(\rho \notin K\) and \(\pi\rho \in K\). Then, \(C(\pi) = C(\pi\rho)\).
4. Let \(\pi \in K\), \(\rho \notin K\) and \(\pi\rho \notin K\). Since \(C(\pi) = \{z_1 \}\) and \(C(\pi) \cap C(\rho) \neq \emptyset\), \(z_1 \in C(\rho)\). Then, we have the following possibilities:
\(\{\rho \} = \{w_1, w_2 \}\). Then, \(C(\rho) = Z\) and \(\{\pi\rho \} = \{w_1, w_2, z_1,z_2 \}\). Hence, \(C(\pi\rho) = Z =C(\rho)\).
\(\{\rho \} = \{ z_1\}, \{\rho \} = \{z_2 \}, \{\rho \} = \{z_1, z_2 \}\) are not possible, since then \(\pi\rho \in K\).
Let \(\rho\) is of type \(T_{4a}\). Then, \(C(\rho) = \{w_1\} \cup Z\) or \(C(\rho) = \{w_2\} \cup Z\). Then, \(C(\pi\rho) = \{w_1\} \cup Z\) or \(C(\pi\rho) = \{w_2\} \cup Z\), respectively. Hence, \(C(\pi\rho) = C(\rho)\).
Let \(\rho\) is of type \(T_{4b}\). Then, \(\{\pi\rho \} = \{w_1, w_2, z_1, z_2 \}\). Hence, \(C(\pi\rho) = Z = C(\rho)\).
Thus, in all cases, (Pre-C) is satisfied. Since \(C(z_1, z_1,z_2) =\{z_1\}\) and \(C(z_1, z_2) = \{z_1, z_2 \}\), \((PI)\) is violated. ◻
This study examines the axiomatic characterization of the center function on fan graphs. While the known universal axioms are sufficient to characterize center function on simple graph classes, they fall short for complex structures. This limitation necessitates the development of specialized axioms that take in the unique properties of these structures. Consequently, this paper, uses a specialized axiom suited for fan graphs to characterize their center function precisely. We characterized the center function on fan graphs using a combination of universal axioms and a new class-specific Totality (T) axiom. This study also identified the independence of the axioms used for the characterization.