Let \(G\) be a connected graph. The center function defined on \(G\) yields a set of vertices that minimizes the maximum distance from the given input vertices. Through axiomatic characterization of the center function, we identify the specific axioms that characterize its behavior on connected graphs. Universal axioms encompass the properties satisfied by the center function on all connected graphs. However, for some graphs, the center function cannot be fully characterized using universal axioms alone. To address this, a set of graph class-specific axioms, known as non-universal axioms, was introduced. In the case of book graphs (Cartesian product of star graph \(K_{1,n}\) and path \(P_2\)), the center function cannot be adequately characterized using known universal axioms. Therefore, in this context, we find an axiomatic characterization of the center function on book graphs using the universal axioms and one newly introduced Cycle Consensus \((CC)\) axiom.
One of the major concerns of location studies is the determination of a location or a set of locations chosen by customers that satisfies certain maximum or minimum optimization criteria. We assume that all customers and their preferred locations are located on the vertices of a finite graph. Additionally, we assume that edges are not assigned any length. To find the center of a graph, one must identify the vertices that minimize the maximum distance to the customers from the vertices. To find the median of a graph, the vertices that minimize the sum of the distances to the customers must be identified, whereas to find the mean of a graph, the vertices that minimize the sum of squares of distances to the customers must be determined. The input for location functions is the customers’ locations, and the output is the set of locations on which they agree. Through axiomatic characterization of the location functions, we aim to identify these functions based on a set of axioms.
Holzman was the first to discover an axiomatic characterization of facility location functions (mean functions) on graphs [9]. Subsequently, Vohra determined the axiomatic characterization of the median function on trees [18]. The mean function on trees was axiomatically characterized by McMorris, Mulder, and Ortega [12]. McMorris, Robert, and Wang characterized the center function on trees [13]. Another proof for the axiomization of the center function on trees was provided by Mulder et al.[16]. The axiomatization of the median function on all median graphs using Anonymity \((A)\), Betweenness \((B)\), and Consistency \((C)\) was presented by Mulder et al. [15]. Using the same axioms, Mulder and Novik characterized the median function on \(n\)-dimensional hypercube, \(Q_n\) [14]. An axiomatic characterization of the antimedian function on finite paths and hypercubes can be found in [1, 17]. Recently, Manoj et al. provided an axiomatic characterization of the median and antimedian functions on cocktail party graphs, complete graphs, and on complete graphs minus a matching [2, 3].
Universal axioms (or class-independent axioms) refer to axioms satisfied by a location function on all connected graphs. For the median function, universal axioms include Anonymity \((A)\), Betweenness \((B)\) and Consistency \((C)\). Meanwhile, Population Invariance \((PI)\), Middleness \((M)\), Pre-Consistency (Pre-C), Quasi-Consistency \((QC)\), Triple Center \((TC)\), and Gatedness \((G)\) were identified as universal axioms for the center function [6]. Axiomatic characterization of the center function on graphs with a dominating vertex, paths, all trees with diameter at most 5, Barbell graphs and \((m,n)\)-lollipops can be accomplished using the aforementioned universal axioms for the center function [5, 6]. Like other location functions the center function cannot be universally characterized across all graph classes using the known universal axioms. To address this, non-universal axioms (or class-dependent axioms) specific to certain graph classes were formulated. By combining these non-universal axioms with universal axioms, the center function on graph classes such as cocktail party graphs, complete bipartite graphs, block graphs, crown graphs and fan graphs were axiomatically characterized [4, 7, 10]. The way in which center function on a graph behaves greatly depends on the structure of the graph on which it is considered. Therefore, when we attempt axiomatic characterization of center function on graphs it is likely that the axioms involved will mirror the structure of the graph considered. This paper attempts to find an axiomatic characterization of the center function on book graphs. Characterizing the center function solely through the known universal axioms is not possible on book graphs. We present an example of a consensus function satisfying the known universal axioms other than the center function. Consequently, we propose a non-universal axiom, namely Cycle Consensus Axiom \((CC)\). By incorporating this non-universal axiom in conjunction with the universal axioms \((PI), (M), (TC)\), and (Pre-C), we characterize the center function on book graphs.
Let \(G = (V(G), E(G))\) be a simple, finite, undirected, connected graph with vertex set \(V(G)\) and edge set \(E(G)\). The distance \(d(u,v)\) between two vertices \(u\) and \(v\) of \(G\) gives the length of a shortest \(u, v\)– path. The interval \(I_G(x, y)\) between \(x\) and \(y\) in \(G\) consists of all vertices on \(x, y\)– shortest paths. When no confusion arises we write \(I\) instead of \(I_G\). A subgraph \(H=(V(H), E(H))\) of \(G=(V(G), E(G))\) is said to be an induced subgraph of \(G\) if each edge of \(G\) having its end vertices in \(V(H)\) is also an edge of \(H\). An induced subgraph \(H\) of \(G\) is denoted by \(\langle H \rangle\). For basic definitions regarding graphs and location functions refer, [8, 11].
For any positive integer \(k\), a profile of length \(k\) is a nonempty sequence \(\pi= (r_1, r_2, \ldots, r_k)\) of the vertices of \(V\). Vertices can be repeated in a profile. The carrier set of \(\pi\), denoted by \(\{ \pi \}\), consists of all the distinct vertices in profile \(\pi\). The number of elements in \(\{\pi \}\) is denoted as \(|\{\pi\}|\). Let \(\pi_1 = (r_1, r_2, \ldots, r_n )\) and \(\pi_2 = (s_1, s_2, \ldots, s_m)\) be any two profiles of lengths \(n\) and \(m\) respectively. The concatenation of \(\pi_1\) and \(\pi_2\) denoted by \(\pi_1 \pi_2\) is the profile \((r_1, r_2, \ldots, r_n, s_1, s_2, \ldots, s_m )\) of length \(n+m\). A single-occurrence profile is a profile \(\pi\) in which each vertex occurs atmost once. The subgraph induced by a profile \(\pi\) is the subgraph with vertex set \(\{\pi \}\) and edge set consists of those edges of \(G\) having both ends in \(\{\pi \}\). Subgraph induced by a profile \(\pi\) is denoted by \(\langle \{\pi \} \rangle\). If \(\pi\) is a single-occurrence profile then the induced subgraph by \(\pi\) is denoted by \(\langle \pi \rangle\).
Let \(V^*\) be the set of all profiles of finite length. A consensus function on graph \(G\) with vertex set \(V\) is a function \(L:V^* \to 2^V-\emptyset\), where \(2^V\) denotes the set of all possible subsets of \(V\). For any profile \((r_1, r_2, \ldots, r_n)\), \(L((r_1, r_2, \ldots, r_n))\) is written as \(L(r_1, r_2, \ldots, r_n)\) for convenience. For any vertex \(v\) of \(G\), we define the maximum distance from \(v\) to profile \(\pi = (r_1, r_2, \ldots, r_n)\) as \(R(v, \pi)= \text{max}\{d(v, r_i) \; |\; 1\leq i\leq n\}\). A vertex \(v\) that minimizes this maximum distance is called the center of \(\pi\). The center function \(Cen\) on \(G\) is the consensus function given by \(Cen(\pi) =\{ v | \text{ v is a center of} \; \pi \}\).
A complete graph is a simple graph where each pair of distinct vertices is joined by an edge. The complete graph on \(n\) vertices is denoted by \(K_n\). A bipartite graph \(G\) is a graph whose vertex set \(V\) can be partitioned into two disjoint sets \(X\) and \(Y\) such that each edge in \(G\) has one end vertex in \(X\) and the other end vertex in \(Y\). The partition \(V=X \cup Y\) is called a bipartition of \(G\). A complete bipartite graph is a bipartite graph with bipartition \(V=X \cup Y\) such that each vertex in \(X\) is joined to every vertex in \(Y\). If \(X\) has \(m\) vertices and \(Y\) has \(n\) vertices, then such a graph is denoted by \(K_{m,n}\). Complete bipartite graph \(K_{1,n}\) is called a star graph. Path \(v_0e_1v_1e_2v_2\ldots e_kv_k\) is a sequence of distinct vertices and edges, beginning and ending with vertices, each edge \(e_i\) is incident with vertices \(v_{i-1}\) and \(v_i\). A path on \(n\) vertices is denoted by \(P_n\).
Universal axioms are axioms satisfied by the center function on all connected graphs, whereas non-universal axioms are axioms satisfied by the center function only on certain classes of graphs. A detailed study of the universal axioms for \(Cen\) can be found in [6]. The following are the universal axioms identified by Changat et al. in [6].
Population Invariance \((PI)\): If \(\pi\) and \(\rho\) are two profiles such that \(\{\pi\} = \{\rho \}\), then \(L(\pi)=L(\rho)\). This means that output depends only on the vertices and not on their multiplicities or position in the profile. Hence if a consensus function \(L\) satisfies \((PI)\), then the profiles considered are single-occurrence profiles.
Middleness (M): \(L(u,v) = Mid(u,v)\), for all vertices \(u, v \in V\), where \(Mid(u, v)\) is defined as follows: \[Mid(u,v) = \begin{cases} \begin{aligned} &\text{middles of}~u, v\text{-geodesics and middles of} \\ &~u,v\text{-paths of length}~d(u,v)+1 \end{aligned}, & \text{if}~d(u,v)~\text{is odd},\\ \text{middles of}~u, v\text{-geodesics}, & \text{if}~d(u,v)~\text{is even}.\\ \end{cases}\]
For an even path \(P=v_0v_1 \cdots v_{2t}\) the middle of \(P\) is \(v_t\), but for an odd path \(P=v_0v_1\cdots v_{2t+1}\) of length \(2t+1\), the middle consists of \(v_t\) and \(v_{t+1}\). Using middleness, the outputs for all profiles of length two can be determined.
Pre-Consistency (Pre-C): If \(\pi\) and \(\rho\) are two profiles such that \(L(\pi) \cap L(\rho) \neq \emptyset\), then \(L(\pi)\cap L(\rho) \subseteq L(\pi \rho) \subseteq L(\pi)\cup L(\rho)\).
Quasiconsistency \((QC)\): If \(L(\pi)= L(\rho)\) for profiles \(\pi\) and \(\rho\), then \(L(\pi \rho) = L(\pi)\). Quasiconsistency follows from (Pre-C).
Besides these axioms, in [6] another axiom Triple Center, was introduced.
Triple Center \((TC)\): \(L(\pi) = Cen(\pi)\), for all profiles of length three. Using this axiom output of all profiles of length three can be obtained.
For details of class-specific axioms used for the characterization of \((Cen)\) on various graph families see, [4, 7, 10].
The book graph \(B_n\) is the Cartesian product of star graph \(K_{1, n}\) and path \(P_2\) on two vertices. Book graph \(B_n\) contains \(2(n+1)\) vertices and \(3n+1\) edges. To draw a book graph \(B_n\) draw two copies of \(K_{1, n}\) and join the corresponding vertices by edges. Let the vertex set of the book graph be denoted by \(V(B_n)=X \cup Y \cup \{u,v\}\), where \(X=\{u_1, u_2, \ldots, u_n \}, Y=\{v_1, v_2, \ldots, v_n \}\) such that \(u_i\) adjacent to \(v_i\), \(u\) adjacent to \(u_i\), \(v\) adjacent \(v_i ,\) and \(u\) adjacent \(v\), where \(i=1,2, \ldots, n\). Vertices \(u\) and \(v\) lie in all 4-cycles of the book graph. Book graph \(B_4\) is given in Figure 1.
Vertices \(u_i\) and \(v_i\) are called pair vertices, \(u_i\) is called the pair of \(v_i\) and vice versa. Hence, book graph \(B_n\) contains \(n\) pairs of pair vertices. Let pair vertex of a vertex \(x\) be denoted by \(x'\). Thus \(u_i'=v_i\) and \(v_i'=u_i\) for \(i=1, 2, \ldots, n\). Vertices \(u_i\) and \(v_j\) where \(i \neq j\) are called unpair vertices. We define the set \(\pi_{XY}\) as follows: \[\pi_{XY} = \begin{cases} \{\pi \} \cap X & \text{if}~ |\{\pi \} \cap X|=1~ \text{and}~ |\{\pi \} \cap Y|\neq 1,\\ \{\pi \} \cap Y & \text{if}~ |\{\pi \} \cap X|\neq 1 ~ \text{and}~ |\{\pi \} \cap Y| = 1,\\ (\{\pi \} \cap X) \cup (\{\pi \} \cap Y) & \text{if}~ |\{\pi \} \cap X|=1 ~ \text{and}~ |\{\pi \} \cap Y| = 1,\\ \emptyset & \text{otherwise}. \end{cases}\]
Also, \(\tilde{\pi}_{XY}\) denote the pair vertices of vertices in \(\pi_{XY}\). For example if \(\pi_1 = (u_1, v_1, v_4,u)\), then \({\pi}_{1_{XY}} = \{u_1 \}\) and \(\tilde{\pi}_{1_{XY}} = \{v_1\}\), if \(\pi_2 =(u_2, v_2, u,v)\), then \({\pi}_{2_{XY}} = \{u_2, v_2\}\) and \(\tilde{\pi}_{2_{XY}} = \{u_2, v_2\}\), if \(\pi_3 =(u_1, v_2, u)\), then \({\pi}_{3_{XY}} = \{u_1, v_2\}\) and \(\tilde{\pi}_{3_{XY}} = \{v_1, u_2 \}\), and if \(\pi_4 =(u_1, u_4, v_2, v_4)\), then \({\pi}_{4_{XY}} = \emptyset\).
Let \(\pi_d\) denote the maximum distance between any two vertices in a profile \(\pi\), that is \(\pi_d = \max \{d(x, y) : x, y \in \{\pi \}\}\). For example if \(\pi = (u_1, v_1, v_2)\), then \(\pi_d =3\). If \(\rho = (u_1, v_1, u, v)\), then \(\rho_d = 2\). For any profile \(\pi\) on book graphs, \(\pi_d \leq 3\). Profiles defined on the book graph \(B_n\) can be classified into the following types:
(a) \(|\{ \pi \}|=1\), or \(|\{\pi \}|=2\) with the condition that \(\{\pi \}\) contains adjacent vertices.
(b) \(|\{\pi \}| \geq 2\) and \(\{\pi \}\) contains at least two non adjacent vertices such that either \(\{\pi \} \subseteq X\cup \{u,v \}\) or \(\{\pi \} \subseteq Y \cup \{u,v \}\).
(c) \(\{\pi \}\) contains exactly one vertex from \(X\) and at least one unpair vertex from \(Y\), or \(\{\pi \}\) contains exactly one vertex from \(Y\) and at least one unpair vertex from \(X\).
(d) \(\{\pi \}\) contains at least two vertices from both \(X\) and \(Y\).
(e) \(\{\pi \} = \{u_i, v_i, x \}\), where \(x \in \{u, v\}\), \(i=1,2, \ldots, n\).
(f) \(\{\pi \}\) contains exactly one pair-vertices, and \(u\) and \(v\), i.e., \(\{\pi \} =\{u_i, v_i, u, v \}\), \(i=1,2, \ldots, n\).
The classification of the profiles \(\pi\) on \(B_n\) is obtained by considering the cases (i) \(\pi_d \leq 1\); (ii) \(\pi_d =2\); (iii) \(\pi_d =3\).
(i) Let \(\pi_d \leq 1\). If \(\pi_d \leq 1\), then \(|\{\pi \}| =1\) or \(\{\pi \}\) contains a pair of adjacent vertices. This consists of profiles of type \((1)\).
(ii) Let \(\pi_d =2\). Then \(\{\pi \}\) does not contain unpair vertices. That is \(\{\pi \}\) contains a vertex adjacent to all vertices in the profile \(\pi\). Then the possible profiles are
\(\bullet\) Profiles in which \(u\) is adjacent to all vertices in the profile \(\pi\). This type of profiles belongs to profiles of type \((2)\).
\(\bullet\) Profiles in which \(v\) is adjacent to all vertices in the profile \(\pi\). This type of profiles belongs to profiles of type \((2)\).
\(\bullet\) Profiles of the type \(\{u_i, v_i, x\}\), where \(x \in \{u,v\}\). This constitutes profiles of type \((5)\).
\(\bullet\) Profiles of the type \(\{u_i, v_i, u, v\}\). This constitutes profiles of type \((6)\).
(iii) Let \(\pi_d =3\). Then \(\pi\) contains unpair vertices. This can be further be divided into \(\pi_{XY} \neq \emptyset\) (profiles of type \((3)\)) or \(\pi_{XY} = \emptyset\), (profiles of type \((4)\)).
Proposition 3.1. For any profile \(\pi\) on book graph \(B_n\),
\[Cen(\pi) = \begin{cases} \{\pi \} & \text{ if } \pi ~\text{is of type}~ (1)\\ \{u \} & \text{ if } \pi~ \text{is of type}~ (2) ~\text{with}~\{\pi \} \subseteq (X\cup \{u,v \}), ~\text{except} ~\{\pi \}=\{v, u_i \} \\ \{u, v_i \} & \text{ if } \{\pi \} = \{v, u_i \}\\ \{v \} & \text{ if } \pi ~\text{is of type} ~(2) ~\text{with}~\{\pi \} \subseteq (Y\cup \{u,v \}), ~ \text{except} ~\{\pi \} = \{u, v_i \}\\ \{v, u_i \} & \text{ if } \{\pi \} = \{u, v_i \}\\ \{u, v \} \cup \tilde{\pi}_{XY} & \text{ if } \pi ~ \text{is of type} ~ (3) ~ \text{or type} ~(6)\\ \{u,v \} & \text{ if } \pi ~ \text{is of type} ~ (4)\\ \{u_i \} & \text{ if } \{\pi\} = \{u_i, v_i, u\} \text{ of type } (5)\\ \{v_i \} & \text{ if } \{\pi\} = \{u_i, v_i, v\} \text{ of type } (5) \end{cases}\]
Proof. Let \(\pi\) be any profile defined on \(B_n\).
(i) Let \(\pi\) is a profile of type \((1)\) with \(|\{\pi \}| =1\). Then \(\{\pi \} = \{x\}, x \in V(B_n)\). So \(Cen(\pi) = \{x\} = \{\pi \}\). Let \(\pi\) is a profile of type \((1)\) with \(|\{\pi \}| =2\). Then \(\{\pi \} = \{x, y\}, x, y \in V(B_n)\) and \(x\) and \(y\) are adjacent vertices. So, \(R(x, \pi) = R(y, \pi) = 1, R(w, \pi) \geq 2\), for every \(w \in (V(B_n)-\{x, y\})\). Hence, \(Cen(\pi) = \{x, y\} =\{\pi \}\).
(ii) Let \(\pi~ \text{is of type}~ (2) ~\text{with}~\{\pi \} \subseteq (X\cup \{u,v \}), ~\text{except} ~\{\pi \}=\{v, u_i \}\). Then \(R(u, \pi) =1\) and \(R(w, \pi) \geq 2\), for every \(w \in (V(B_n) – \{u\})\). Hence, \(Cen(\pi) = \{u\}\).
(iii) Let \(\{\pi \} = \{v, u_i\}\). Then \(R(u, \pi) = 1\), \(R(u_i', \pi) =1, R(w, \pi) = 2\), for all \(w \in X\) and \(R(w, \pi) =3\), for all \(w \in (Y-\{v_i\})\). Thus, \(Cen(\pi) = \{u, u_i'\} = \{u, v_i\}\).
(iv) Let \(\pi~ \text{is of type}~ (2) ~\text{with}~\{\pi \} \subseteq (Y\cup \{u,v \}), ~\text{except} ~\{\pi \}=\{u, v_i \}\). Then \(R(v, \pi) =1\) and \(R(w, \pi) \geq 2\), for every \(w \in (V(B_n) – \{v\})\). Hence, \(Cen(\pi) = \{v\}\).
(v) Let \(\{\pi \} = \{u, v_i\}\). Then \(R(v, \pi) = 1\), \(R(v_i', \pi) =1, R(w, \pi) = 2\), for all \(w \in Y\) and \(R(w, \pi) =3\), for all \(w \in (X-\{u_i\})\). Thus, \(Cen(\pi) = \{v, v_i'\} = \{v, u_i\}\).
(vi) Let \(\pi\) be a profile of type \((3)\) or type \((6)\). Then \(R(u, \pi) = R(v, \pi) = 2\), \(R(w, \pi) = 2, w \in \tilde{\pi}_{XY}\), and \(R(w, \pi) = 3, w \in (V(B_n) – (\{u, v\} \cup \tilde{\pi}_{XY}))\). Hence, \(Cen(\pi) = \{u,v\} \cup \tilde{\pi}_{XY}\).
(vii) Let \(\pi\) be a profile of type \((4)\). Then \(R(u, \pi) = R(v, \pi) =2\), and \(R(w, \pi) =3\), for all \(w \in (X \cup Y)\). Thus \(Cen(\pi) = \{u, v\}\).
(viii) Let \(\pi\) be a profile of type \((5)\) with \(\{\pi \} =\{u_i, v_i, u\}\). Then \(R(u_i, \pi) = 1\), \(R(u, \pi) = R(v, \pi) =R(v_i, \pi) = 2\), and \(R(w, \pi) =3\), for all \(w \in (V(B_n) – (\{\pi \} \cup \{v\} )\). Hence, \(Cen(\pi) = \{u_i\}\). Similarly, let \(\pi\) be a profile of type \((5)\) with \(\{\pi \} =\{u_i, v_i, v\}\). Then \(R(v_i, \pi) = 1\), \(R(u, \pi) = R(v, \pi) =R(u_i, \pi) = 2\), and \(R(w, \pi) =3\), for all \(w \in (V(B_n) – (\{\pi \} \cup \{u\} )\). Hence, \(Cen(\pi) = \{v_i\}\). ◻
We provide a characterisation based on the six profile types introduced above. Profiles of types \((1), (2),\) and \((5)\) are shown to satisfy the characterization directly using the universal axioms. Type (6) is handled separately using axiom (CC). Type (3) is resolved through Lemma 6, while type (4) is treated using Lemma 3. Together, these arguments cover all admissible profiles and complete the proof of the main result.
Lemma 3.2. Let \(L\) be a consensus function defined on the book graph \(B_n\). If \(L\) satisfies \((PI), (M)\) and (Pre-C) for any profile \(\pi\) of type \((5)\), then \(L(\pi) = Cen(\pi)\).
Proof. Let \(\pi\) be a profile of type \((5)\). Without loss of generality, assume that \(\{\pi \}=\{u_i, v_i, u \}\). Therefore, \(L(u, u_i)=\{u, u_i \},L(u, v_i)=\{u_i, v \}\) and \(L(u_i, v_i)=\{u_i, v_i \}\). So, \(L(u, u_i) \cap L(u, v_i) = L(u, u_i) \cap L(u_i, v_i)= L(u, v_i) \cap L(u_i, v_i) =\{ u_i\} \neq \emptyset.\) Hence by \((PI)\) and (Pre-C), we have \(\{u_i \} \subseteq L(u, u_i, v_i) \subseteq \{u, v, u_i \}, \{u_i \} \subseteq L(u, u_i, v_i) \subseteq \{v, u_i, v_i \}, \{u_i \} \subseteq L(u, u_i, v_i) \subseteq \{u, u_i, v_i \}\). Thus, \(L(u, u_i, v_i)=\{u_i \} = Cen(u, u_i, v_i)\). In a similar manner, we can prove that if \(\{\pi \} = \{u_i, v_i, v \}\), and if \(L\) satisfies \((PI), (M)\) and (Pre-C), then \(L(\pi) = Cen(\pi)\). ◻
Lemma 3.3. Let \(L\) be a consensus function defined on the book graph \(B_n\). If \(L\) satisfies \((PI), (M)\) and (Pre-C), \(L(\pi) =Cen(\pi)\) for any profile of type \((2)\).
Proof. Let \(\pi\) be a profile of type \((2)\). For any profile \(\pi\) with \(|\{\pi \}| \leq 2\), by \((PI)\) and \((M),\) \(L(\pi)= Cen(\pi)\). Without loss of generality, let \(\{\pi \} \subseteq (X \cup \{u, v \})\). Let \(\pi =(x_1, x_2, \ldots, x_n)\) be any profile of length \(n\). We use mathematical induction on \(n\) to prove that \(L(\pi) = Cen(\pi)\). Let \(|\{\pi \}| = 3\) and let \(\pi=(x_1, x_2, x_3)\). Without loss of generality, let \(x_1=u_1, x_2=u_2\). Then, for \(x_3\) there are three possibilities.
(i) \(x_3=u,\)
(ii) \(x_3=v,\)
(iii) \(x_3=u_i, i=3, 4, \ldots, n\).
Case 1. When \(x_3=u\). Then \(\{\pi \}=\{u_1, u_2, u \}\). \(L(u_1, u_2)= \{u \},L(u_1, u)=\{u_1, u \},L(u_2, u) =\{u_2, u \}\). Thus, \(L(u_1, u_2) \cap L(u_1, u) \cap L(u_2, u) = \{u\} \neq \emptyset\). Then by \((PI)\) and (Pre-C), we have \(\{u \} \subseteq L(u_1, u_2, u) \subseteq \{u, u_1 \}\), \(\{u \} \subseteq L(u_1, u_2, u) \subseteq \{u, u_2 \}\) and \(\{u \} \subseteq L(u_1, u_2, u) \subseteq \{u, u_1, u_2 \}\). Therefore, \(L(u, u_1, u_2)=\{u\}=Cen(u, u_1, u_2)\).
Case 2. When \(x_3=v\). Then \(\{\pi \} = \{u_1, u_2, v \}\). By \((PI)\) and \((M)\), \(L(u_1, u_2) = \{u\},L(u_1, v) =\{u, v_1 \},L(u_2, v)=\{u, v_2 \}\). Since \(L(u_1, u_2) \cap L(u_1, v) \cap L(u_2, v) = \{u\} \neq \emptyset\), by \((PI)\) and (Pre-C), \(\{u\} \subseteq L(u_1, u_2, v) \subseteq \{u, v_1 \}, \{u\} \subseteq L(u_1, u_2, v) \subseteq \{u, v_1, v_2 \}, \{u\} \subseteq L(u_1, u_2, v) \subseteq \{u, v_2 \}\). Therefore, \(L(u_1, u_2, v) =\{u \} =Cen(u_1, u_2, v)\).
Case 3. When \(x_3=u_i, i= 3, 4, \ldots, n\). Then \(\{ \pi \}= \{u_1, u_2, u_i \}\). By \((M)\), \(L(u_1, u_2)=\{u\},L(u_1, u_i)=\{u\},L(u_2, u_i)=\{u\}\). Since \(L(u_1, u_2) \cap L(u_1, u_i) \cap L(u_2, u_i) = \{u\} \neq \emptyset, i=3, 4, \ldots, n\), by \((PI)\) and (Pre-C), \(L(u_1, u_2, u_i)=\{u\} =Cen(u_1, u_2, u_i), i=3, 4, \ldots, n\).
Also if \(\pi = \{ u_i, u, v \}\), by \((M)\), \(L(u, v) =\{u, v \},L(u, u_i) = \{u, u_i \},L(v, u_i) = \{u, v_i \}\). Since \(L(u, v) \cap L(u, u_i) \cap L(v, u_i) =\{u\} \neq \emptyset\), by \((PI)\) and (Pre-C), \(\{u \} \subseteq L(u, v, u_i) \subseteq \{u, v, u_i\}, \{u \} \subseteq L(u, v, u_i) \subseteq \{u, u_i, v_i\}, \{u \} \subseteq L(u, v, u_i) \subseteq \{u, v, v_i\}\). Hence, \(L(u, v, u_i) = \{ u\}\).
Thus, in all the cases, \(L(\pi) = Cen(\pi)\) if \(|\{\pi \}| =3\). Suppose that \(L(\pi) =Cen(\pi)\) for all profiles of type \((2)\) with \(|\{\pi \}| \leq n-1\). Let \(\pi=(x_1, x_2, \dots, x_n)\) be any profile of length \(n\). Let \(x_1\) and \(x_2\) be nonadjacent vertices in \(X\cup \{u, v \}\). Then by the above arguments \(L(x_1, x_2, \dots, x_{n-1}) = Cen(x_1, x_2, \dots, x_{n-1})=\{u\},L(x_1, x_2, x_4, \dots, x_n)\\ = Cen(x_1, x_2, x_4, \dots, x_n)=\{u\}\). Since \(L(x_1, x_2, \dots, x_{n-1}) \cap L(x_1, x_2, x_4, \dots, x_n) =\{u\} \neq \emptyset\), by \((PI)\) and (Pre-C), \(L(x_1, x_2, \dots, x_n)=\{u\}= Cen(x_1, x_2, \dots, x_n)\).
Similarly, if \(\pi\) is a profile of type \((2)\), with \(\{\pi \} \subseteq Y \cup \{u, v\}\), we can prove that \(L(\pi)=Cen(\pi)\). ◻
Lemma 3.4. Let \(L\) be a consensus function defined on the book graph \(B_n\). Let \(L\) satisfies \((PI), (M)\) and (Pre-C) and let \(L(\pi)=Cen(\pi)\) for any profile of type \((3)\). Then, \(L(\pi)=Cen(\pi)\) for any profile of type \((4)\).
Proof. Let \(\pi\) be a profile of type \((4)\). Then \(\pi\) contains at least two vertices from both \(X\) and \(Y\). Let \(\{\pi \} =\{u_i, u_j, v_k, v_{\ell} \}\) where \(i \neq j, k\neq \ell\). Since \(L(\pi)=Cen(\pi)\) for profiles of type \((3)\), \(L(u_i, u_j, v_k) = \{u,v\} \cup \tilde{\pi}_{XY} =\{u, v, v_k' \},L(u_i, u_j, v_{\ell})=\{u,v\} \cup \tilde{\pi}_{XY} = \{u, v, v_{\ell}' \}\). Since \(L(u_i, u_j, v_k) \cap L(u_i, u_j, v_{\ell}) =\{u,v\} \neq \emptyset\), by \((PI)\) and (Pre-C), \[\label{eq2} \{u, v \} \subseteq L(u_i, u_j, v_k, v_{\ell}) \subseteq \{u, v, v_k', v_{\ell}' \}, \tag{1}\]
Also, \(L(v_k, v_{\ell}, u_i) = \{u,v\} \cup \tilde{\pi}_{XY} =\{u, v, u_i' \},L(v_k, v_{\ell}, u_j) = \{u,v\} \cup \tilde{\pi}_{XY} =\{u, v, u_j' \}\). Since \(L(v_k, v_{\ell}, u_i) \cap L(v_k, v_{\ell}, u_j) =\{u,v\} \neq \emptyset\), by \((PI)\) and (Pre-C), \[\label{eq3} \{u, v \} \subseteq L(u_i, u_j, v_k, v_\ell) \subseteq \{u, v, u_i', u_j' \}. \tag{2}\]
Hence, from (1) and (2), \(L(u_i, u_j, v_k, v_\ell) =\{u, v \}\). Let \(\pi\) be any profile of type \((4)\) with \(|\{\pi \} |> 4\) and let \(\pi = (x_1, x_2, \ldots, x_n)\). Without loss of generality, let \(x_1, x_2 \in X\) and \(x_3, x_4 \in Y\). Now \[\label{1} L(x_1, x_2, x_3, x_4)=\{u, v \} . \tag{3}\]
If \(x_5 \in X\), then \[\label{2} L(x_1, x_3, x_4, x_5)=\{u, v \} . \tag{4}\]
Since \(L(x_1, x_2, x_3, x_4) \cap L(x_1, x_3, x_4, x_5) = \{u,v\} \neq \emptyset\), by \((PI)\) and (Pre-C), from (3) and (4) we get \(L(x_1, x_2, x_3, x_4, x_5)=\{u, v \}\). If \(x_5 \in Y\), then \[\label{3} L(x_1, x_2, x_3, x_5)=\{u, v \} . \tag{5}\]
Since \(L(x_1, x_2, x_3, x_4) \cap L(x_1, x_2, x_3, x_5) =\{u,v\} \neq \emptyset\), by \((PI)\) and (Pre-C), from (3) and (5) we get \(L(x_1, x_2, x_3, x_4, x_5)=\{u, v \}\).
If \(x_5 \in \{u, v \}\) then \[ L(x_1, x_2, x_3, x_5)=\{u, v, x_3^{'} \},~L(x_1, x_2, x_4, x_5)=\{u, v, x_4^{'} \} \label{eq:1}, \ \tag{6}\] \[L(x_1, x_3, x_4, x_5)=\{u, v, x_1^{'} \},~L(x_2, x_3, x_4, x_5)=\{u, v, x_2^{'} \} \label{eq:2} , \tag{7}\] where \(x_1^{'}, x_2^{'}, x_3^{'}\) and \(x_4^{'}\) are pairs of vertices \(x_1, x_2, x_3\) and \(x_4\) respectively. From (6) and (7), since \(L(x_1, x_2, x_3, x_5) \cap L(x_1, x_3, x_4, x_5) =\{u,v\} \neq \emptyset\), by \((PI)\) and (Pre-C), \(L(x_1, x_2, x_3, x_4, x_5)=\{u, v \}\).
Proceeding in this way, we obtain \(L(x_1, x_2, \ldots, x_n)=\{u, v \} = Cen(x_1, x_2, \ldots, x_n)\). ◻
Lemma 3.5. Let \(\pi\) be a profile of type \((3)\) defined on book graph \(B_n\). Then, \(\pi \rho\) will be of type \((3)\) or type \((4)\) for any profile \(\rho\).
Proof. Let \(\pi\) be any profile of type \((3)\). We consider the following cases:
Case 1. Let \(\{\pi\} = \{u_i, v_j\}, i \neq j\). If \(\{\rho\} \subseteq \{u, v\}\), then \(\pi\rho\) will be of type \((3)\). Similarly, if \(\{\rho\} \subseteq X\) or \(\{\rho\} \subseteq Y\), then \(\pi\rho\) will be of type \((3)\). But if \(\{\rho\} \cap (X-\{u_i\}) \neq \emptyset\) and \(\{\rho\} \cap (Y-\{v_j\}) \neq \emptyset\), then \(\pi\rho\) will be of type \((4)\). Similar is the case when \(\{\pi \} = \{u, u_i, v_j\}\) or when \(\{\pi \} = \{u, v, u_i, v_j\}\), where \(i \neq j\).
Case 2. Let \(\{\pi\}\) contains exactly one vertex say \(u_i \in X\) and at least one unpair vertex say \(v_j \in Y\) and \(|\{\pi\} \cap Y| \geq 2\). In this case, if \(\{\rho\} \subset \{u, v\}\), then \(\pi\rho\) will be of type \((3)\). If \(|\{\rho\} \cap (X-\{u_i\})|\geq 2\), then \(\pi\rho\) will be of type \((4)\). However, if \(\{\rho\} \subseteq Y\), then \(\pi\rho\) will be of type \((3)\).
Case 3. Let \(\{\pi\}\) contains exactly one vertex from \(Y\) and at least one unpair vertex from \(X\) and \(|\{\pi\} \cap X| \geq 2\). Then, as in Case 2, we can prove that \(\pi\rho\) will be of type \((3)\) or type \((4)\). ◻
Lemma 3.6. Let \(\pi\) be any profile of type \((3)\) defined on book graph \(B_n\). Then \(Cen(\pi \rho) \subseteq Cen(\pi)\), for any profile \(\rho\) defined on \(B_n\).
Proof. For any profile \(\rho\), if \(\pi\) is of type \((3)\), then by Lemma 3.5, \(\pi\rho\) will be of type \((3)\) or type \((4)\).
Case 1. Let \(\pi\rho\) be of type \((4)\). Then \(Cen(\pi\rho) = \{u, v\}\). Since \(\pi\) is of type \((3)\), \(\{u, v\} \subseteq Cen(\pi)\). Hence, \(Cen(\pi\rho) \subseteq \{u, v\} \subseteq Cen(\pi)\).
Case 2. Let \(\pi\rho\) be of type \((3)\). If \(x \in Cen(\pi\rho)\), then \(R(x, \pi\rho) = 2.\) Since \(R(x, \pi) \leq R(x, \pi\rho)\), \(R(x, \pi) \leq 2\). Since \(\pi\) is of type \((3)\), \(R(u, \pi) = R(v, \pi) = 2\), \(R(w, \pi) = 2, w \in \tilde{\pi}_{XY}\), and \(R(w, \pi) = 3, w \in (V(B_n) – (\{u, v\} \cup \tilde{\pi}_{XY}))\). Thus, \(R(x, \pi) \geq 2\). Therefore \(R(x, \pi) =2\). Hence, \(x \in Cen(\pi)\). Thus, \(Cen(\pi\rho) \subseteq Cen(\pi)\). ◻
Now, let us examine a consensus function defined on book graphs. This function satisfies all the known universal axioms of \(Cen\). However, this function is distinct from the center function.
Example 3.7. Let \(L\) be a consensus function defined on book graph \(B_n, n \geq 3\) as follows\[L(\pi) = \begin{cases} \{u_i, v_i \} & \text{if} ~ \{ \pi\} = \{u, v, u_i, v_i \},~\text{where}~ i=1,2, \dots, n,\; \text{ profile of type (6)}, \\ Cen(\pi) & otherwise. \end{cases}\]
Claim 1. \(L\) satisfies the axioms \((PI), (M)\), (Pre-C), and \((TC)\).
Proof. \(L(u, v, u_1, v_1) = \{u_1, v_1 \} \neq \{u, v, u_1, v_1 \} =Cen(u, v, u_1, v_1)\), hence \(L \neq Cen\). For any profiles \(\pi\) and \(\rho\) with \(\{\pi \} =\{\rho \}\), \(L(\pi) =L(\rho)\). Hence \(L\) satisfies \((PI)\). For profile \(\pi\) with \(\{\pi \} =\{x, y\}\), \(L(\pi) = Cen(\pi) = \{x, y\}\), hence \((M)\) is satisfied. For profiles \(\pi\) of length three, by the definition of \(L\), \(L(\pi) = Cen(\pi)\). Thus \((TC)\) is satisfied. We now prove that \(L\) satisfies (Pre-C). For that, we consider the following cases:
Case 1. Let both \(\pi\) and \(\rho\) are of type \((6)\).
Then \(\pi\rho\) can be of type \((4)\) or type \((6)\). If \(\pi\rho\) is of type \((4)\), then \(L(\pi) \cap L(\rho) = \emptyset\). If \(\pi\rho\) is of type \((6)\), then \(\{\pi \} =\{\rho \} =\{\pi\rho \}\). Thus \(L(\pi) = L(\rho)= L(\pi\rho)\). Hence, (Pre-C) is satisfied.
Case 2. Let both \(\pi\) and \(\rho\) are not of type \((6)\).
Then, \(\pi\rho\) cannot be of type \((6)\) with \(L(\pi) \cap L(\rho) \neq \emptyset\). Hence, in that case \(L(\pi) = Cen(\pi),L(\rho) =Cen(\rho),L(\pi\rho) = Cen(\pi\rho)\). Since \(Cen\) satisfies (Pre-C), (Pre-C) is satisfied.
Case 3. Let \(\pi\) be of type \((6)\) and \(\rho\) not of type \((6)\).
Without loss of generality, assume that \(\{\pi\} =\{u, v, u_i, v_i \}\). Then \(L(\pi) = \{u_i, v_i\}\). Now the following cases occurs: If \(\rho\) is of type \((1)\), then since \(L(\pi) \cap L(\rho) \neq \emptyset\), \(\{\rho \} \subseteq \{\pi \}\). Thus, \(\{\pi\} =\{\pi\rho \}\). Hence, \(L(\pi) = L(\pi\rho)\). So, (Pre-C) is satisfied. If \(\rho\) is of type \((2)\), except \(\{\rho \} =\{u_i, v \}\) or \(\{\rho \} = \{v_i, u\}\), then \(L(\rho) = \{u\}\) or \(L(\rho) = \{v\}\). Then \(L(\pi) \cap L(\rho) =\emptyset\). Also, if \(\rho\) is of type \((4)\) then \(L(\rho) = \{u,v \}\). Then \(L(\pi) \cap L(\rho) = \emptyset\). If \(\rho\) is of type \((2)\) with \(\{\rho \} = \{u_i, v \}\) or \(\{\rho \} = \{v_i, u \}\) or \(\rho\) is of type \((5)\), then \(\{\pi\rho \} = \{\pi \}\). So, \(L(\pi\rho) = L(\pi)\). Hence, (Pre-C) is satisfied. Let \(\rho\) be a profile of type \((3)\). Since, \(L(\pi) \cap L(\rho) \neq \emptyset\), either \(u_i \in L(\rho)\) or \(v_i \in L(\rho)\). Then either we have \(\{\rho \} \cap X =\{u_i\}\) or \(\{\rho \} \cap Y =\{v_i\}\). Let \(\{\rho \} \cap X =\{u_i\}\). Then \(L(\pi) \cap L(\rho) =\{v_i\} \neq \emptyset\) and since \(\rho\) is a profile of type \((3)\), \(\{\rho \} \cap (Y-\{v_i\}) \neq \emptyset\). Hence, \(\pi\rho\) is a profile of type \((3)\) with \(\{\pi\rho \} \cap X = \{u_i \}\) and \(\{\pi\rho \} \cap (Y-\{v_i\}) \neq \emptyset\). So, \(v_i \in L(\pi\rho)\). Thus \(L(\pi) \cap L(\rho) = \{v_i\} \subseteq L(\pi\rho)\) and \(L(\pi\rho) \subseteq L(\rho)\). Hence, (Pre-C) is satisfied. Similar is the case when \(\{\rho \} \cap Y = \{v_i\}\).
Case 4. Let \(\rho\) be of type \((6)\) and \(\pi\) not of type \((6)\). As in Case 3, we can prove that (Pre-C) is satisfied.
Hence, in all cases (Pre-C) is satisfied. ◻
Since there exists functions other than center function on book graphs that satisfy universal axioms, we cannot characterize \(Cen\) on book graphs using the known universal axioms. So, in order to overcome this we introduce the new axiom namely, Cycle Consensus Axiom defined as follows:
For any profile \(\pi\), if the subgraph induced by \(\{\pi\}\) is cycle \(C_n\), then \(L(\pi) = \{\pi\}\).
The axiom states that if the subgraph induced by a profile is a cycle, then the output consists of all distinct vertices in the profile.
Evidently, \((CC)\) is not a universal axiom for the center function. Consider a complete bipartite graph with bipartition \(V=X \cup Y\), where \(X=\{x_1, x_2, x_3\}\) and \(Y=\{y_1, y_2, y_3\}\). Let \(\{\pi\} = \{x_1, x_2, y_1, y_2\}\). Then the subgraph induced by \(\{\pi\}\) is a \(4\)-cycle. But \(Cen(\pi) = V \neq \{\pi\}\). Let \(\pi\) be any profile defined on book graph \(B_n\). Then \(\langle \{\pi \}\rangle\) is a cycle only if \(\pi\) is a profile of type \(6\). For any profile of type \(6\), that is \(\{\pi\} = \{u, v, u_i, v_i\}\), for some \(i\), defined on \(B_n\), \(\langle \{\pi\} \rangle\) is a \(4\)-cycle. Hence for any profile of type \(6\) defined on \(B_n\), \(Cen(\pi) = Cen(u, v, u_i, v_i) = \{u, v, u_i, v_i\} = \{\pi \}\). Thus, \(Cen\) satisfies \((CC)\) on book graph \(B_n\).
Lemma 3.8. Let \(L\) be a consensus function defined on book graph \(B_n\) satisfying \((PI), (M),\) (Pre-C), \((TC)\) and \((CC)\) axioms. Then \(L(\pi) = Cen(\pi)\), for any profile \(\pi\) of type \((3)\).
Proof. Let \(\pi = (x_1, x_2, \ldots, x_n)\) be a profile of type \((3)\). If \(|\{\pi\}| \leq 2\), then by \((PI)\) and \((M)\), \(L(\pi)=Cen(\pi)\). If \(|\{\pi\}| = 3\), then by \((TC)\), \(L(\pi) = Cen(\pi)\). So, we consider the cases when \(|\{\pi\}| \geq 4\).
Case 1. Let \(\{\pi\} \cap X = \{u_i\}\) and \(\{\pi\}\) contains at least one unpair vertex from \(Y\).
Subcase i. Let \(| \{\pi\} \cap \{u, v\}| =0\). Without loss of generality, let \(x_1 =u_i\). Then \(L(x_1, x_2, x_k) =\{x_1', u, v\} = \{v_i, u, v\}, k=3,4, \ldots, n\). Since, \(\cap_{k=3}^{n}L(x_1, x_2, x_k) =\{v_i, u, v\} \neq \emptyset\) , by \((PI)\) and (Pre-C), \(L(x_1, x_2, \ldots, x_n) = \{v_i, u,v\} = Cen(\pi)\).
Subcase ii. Let \(|\{\pi\} \cap \{u, v\}| = 1\). Without loss of generality, let \(x_1=u_i, x_2 \in \{u, v\}, x_3 \in (Y-\{v_i\})\). By \((TC)\), \[\begin{aligned} L(x_1, x_2,x_3) = \{u, v, x_1', x_3'\} = \{u, v, v_i, x_3'\},\\ L(x_1, x_3, x_4) = \{v_i, u, v\}, L(x_2, x_3, x_4) = \{v\}. \end{aligned}\]
Since \(L(x_1, x_2,x_3) \cap L(x_1, x_3, x_4) \cap L(x_2, x_3, x_4) =\{v\} \neq \emptyset\), by \((PI)\) and (Pre-C), we have \[\begin{aligned} \{u, v, v_i\} \subseteq L(x_1, x_2, x_3, x_4) \subseteq \{u, v, v_i, x_3'\}, \\ \{v\} \subseteq L(x_1, x_2, x_3, x_4) \subseteq \{u, v, v_i\}. \end{aligned}\]
Hence, \(L(x_1, x_2, x_3, x_4) = \{u, v, v_i\} = Cen(x_1, x_2, x_3, x_4)\). Thus, in general, \(L(x_1, x_2, x_3, x_k) = \{u_i, u, v\}, k=4, 5, \ldots, n\). Since \(\cap_{k=4}^{n}L(x_1, x_2, x_3, x_k) =\{u_i,u,v\} \neq \emptyset\), by \((PI)\) and (Pre-C), \(L(x_1, x_2, \ldots, x_n) = \{u_i, u, v\} = Cen(x_1, x_2, \ldots, x_n)\).
Subcase iii. Let \(|\{\pi\} \cap \{u, v\}| =2\). Let \(\pi = (u_i, v_j, u, v)\). If \(i=j\), then by \((CC)\), \(L(\pi) = \{u_i, v_i, u, v\}\). If \(i \neq j\), then by \((TC)\), \[\begin{aligned} L(u_i, v_j, u) = \{u, v, v_i, u_j\},L(u_i, v_j, v) = \{u, v, v_i, u_j\}. \end{aligned}\]
Since \(L(u_i, v_j, u) \cap L(u_i, v_j, v) = \{u, v, v_i, u_j\} \neq \emptyset\), by \((PI)\) and (Pre-C), \[L(u_i, v_j, u, v) = \{u, v, v_i, u_j\} = Cen(u_i, v_j, u, v).\]
Thus \[\label{eq8} L(u_i, v_j, u, v) = \{u, v\} \cup \{u_i', v_j'\}. \tag{8}\]
Now let \(\pi = (x_1, x_2, x_3, x_4, x_5)\). Without loss of generality, let \(x_1=u_i, x_2=u, x_3=v\) and \(x_4, x_5\in Y\). By \((TC)\), \[\label{eq9} L(x_1, x_4, x_5) = \{v_i, u, v\}. \tag{9}\]
Also, from (8), \[ L(x_1, x_2, x_3, x_4) =L(u_i, u, v, x_4) =\{u_i', u, v, x_4'\} = \{v_i, u, v, x_4'\} \label{eq10},\ \tag{10}\] \[L(x_1, x_2, x_3, x_5) =L(u_i, u, v, x_5) =\{u_i', u, v, x_5'\} = \{v_i, u, v, x_5'\} \label{eq11}, \tag{11}\] where \(x_4'\) and \(x_5'\) are the pair vertices of \(x_4\) and \(x_5\) respectively.
Since \(L(x_1, x_4, x_5) \cap L(x_1, x_2, x_3, x_4) \cap L(x_1, x_2, x_3, x_5) =\{v_i, u, v\} \neq \emptyset\), by \((PI)\) and (Pre-C), from Eqs. (9), (10), (11) \[\begin{aligned} \{v_i, u, v\} \subseteq L(\pi) \subseteq \{v_i, u, v, x_4'\} ,\\ \{v_i, u, v\} \subseteq L(\pi) \subseteq \{v_i, u, v, x_5'\}. \end{aligned}\]
Hence, \(L(x_1, x_2, x_3, x_4, x_5) = \{v_i, u, v\} = Cen(x_1, x_2, x_3, x_4, x_5)\).
Thus, in general, \(L(x_1, x_2, x_3, x_4,
x_k) = \{v_i, u, v\}, k=5,6, \ldots, n\). Since
\(\cap_{k=5}^{n}L(x_1, x_2, x_3, x_4, x_k) =
\{v_i, u, v\} \neq \emptyset\), by \((PI)\) and (Pre-C), \(L(x_1, x_2, \ldots, x_n) = \{v_i, u, v\}\\=
Cen(x_1, x_2, \ldots, x_n)\). Thus, \(L(\pi) = Cen(\pi)\).
Case 2. Let \(\{\pi \} \cap Y = \{v_i\}\) and \(\{\pi \}\) contains at least one unpair vertex from \(X\).
Proceeding as in Case 1, we can prove that \(L= Cen\). ◻
Theorem 3.9. Let \(L\) be a consensus function defined on the book graph \(B_n\). Then \(L=Cen\) if and only if \(L\) satisfies \((PI), (M)\), (Pre-C), \((CC)\) and \((TC)\).
Proof. Let \(L\) satisfies \((PI), (M)\) and (Pre-C). Then, \(L(\pi)=Cen(\pi)\) for all profiles of type \((1), (2)\) and \((5)\). By \((CC)\), \(L(\pi) = Cen(\pi)\) for any profile \(\pi\) of type \((6)\). From Lemma 3.8, \(L(\pi)=Cen(\pi)\) for all profiles of type \((3)\). By Lemma 3.4, \(L(\pi) = Cen(\pi)\) for all profiles of type \((4)\). Thus, in all cases, \(L(\pi) =Cen(\pi)\), for any profile \(\pi\) defined on book graph \(B_n\). Conversely, if \(L(\pi) = Cen(\pi)\), for any profile \(\pi\) defined on book graph \(B_n\), then by the definition of \(Cen\), \(L\) satisfies, \((PI), (M)\), (Pre-C), \((CC)\) and \((TC)\). ◻
The following examples demonstrate the independence of the axioms used in the Theorem 3.9.
Example 4.1(Not \((PI)\)).Let \(\pi =(x_1, x_2, \ldots, x_n)\) be a profile defined on book graph \(B_n\) as follows: \[L(\pi) = \begin{cases} \{u \} & { \text{ if } x_1=x_2=x_3=u \text{ and }~ \{\pi \} = \{u, u_i\} \text{ or } \{\pi \} = \{u,v\} \text{ where } i=1, 2, \ldots n , } \\ Cen(\pi) & otherwise. \end{cases}\]
Claim 2. \(L\) satisfies \((M)\), (Pre-C), \((CC)\) and \((TC)\), but not \((PI)\).
Proof. Let \(\pi = (u, u,u, u_1)\) and \(\rho = (u, u_1)\). Then \(\{\pi \} = \{\rho \} = \{u, u_1\}\). But \(L(\pi) =\{u\} \neq L(\rho) = Cen(u, u_1) = \{u, u_1\}\). Thus, \((PI)\) is violated. If \(\langle \{\pi \} \rangle = C_n\), then \(\{\pi\} = \{u, v, u_i, v_i\}\). Since \(\{\pi\} = \{u, v, u_i, v_i\}\) then, \(L(\pi) = Cen(\pi) = \{\pi \}\). Hence, \((CC)\) is satisfied. For any profile of length three, \(L(\pi)= Cen(\pi)\). Thus \((TC)\) is satisfied. Also \(L(x, y) = Cen(x, y) =\{x,y\}\). Hence, \((M)\) is satisfied. Now we prove that (Pre-C) is satisfied. For any profile \(\pi\), \(L(\pi) \subseteq Cen(\pi)\). For profiles \(\pi\) with \(L(\pi) \neq Cen(\pi)\), \(L(\pi) =\{u\}\) and \(Cen(\pi) = \{u, u_i\}\) or \(Cen(\pi) = \{u,v\}\). Thus, \(L(\pi) \subseteq Cen(\pi)\). Let \(\pi\) and \(\rho\) be two profiles with \(L(\pi) \cap L(\rho) \neq \emptyset\).
Case 1. Let \(L(\pi\rho)\neq Cen(\pi\rho)\).
Therefore, \(L(\pi\rho) = \{u\}\) and \(Cen(\pi\rho) = \{u, u_i\}\) or \(Cen(\pi\rho) = \{u, v\}\). Since \(L(\pi\rho) \neq Cen(\pi\rho)\), \(\pi = (u)\) or \(\pi = (u, u)\) or \(\pi = (u, u,u)\) or \(\pi = (x_1, x_2, \ldots, x_n)\), with \(x_1=x_2=x_3=u\) and \(\{\pi \} = \{u, u_i\}\) or \(\{\pi \} =\{u,v\}\). Hence, \(L(\pi) =\{u\}\). So, \(L(\pi) \cap L(\rho) = \{u\} = L(\pi\rho) \subseteq L(\pi) \cup L(\rho)\). Thus, (Pre-C) is satisfied.
Case 2. Let \(L(\pi\rho) = Cen(\pi\rho)\).
Since \(L(\pi) \subseteq Cen(\pi)\) and \(L(\rho) \subseteq Cen(\rho)\), we have \(L(\pi) \cap L(\rho) \subseteq Cen(\pi) \cap Cen(\rho) \subseteq Cen(\pi\rho) = L(\pi\rho)\). Thus, the first inclusion of (Pre-C) is satisfied. Now we will prove that \(L(\pi\rho) \subseteq L(\pi) \cup L(\rho)\).
Subcase i. Let \(L(\pi) =Cen(\pi)\) and \(L(\rho) = Cen(\rho)\).
Then \(L(\pi\rho) = Cen(\pi\rho) \subseteq Cen(\pi) \cup Cen(\rho) =L(\pi) \cup L(\rho)\). Thus, (Pre-C) is satisfied.
Subcase ii. Let \(L(\pi) \neq Cen(\pi)\).
Therefore, \(\pi = (x_1, x_2,\ldots, x_n)\) with \(x_1 = x_2 =x_3= u, \{\pi \} = \{u, u_i \}\) or \(\{u, v \}\) and \(L(\pi) =\{u \}\). Now we have either \(L(\rho) \neq Cen(\rho)\) or \(L(\rho) = Cen(\rho)\).
Let \(L(\rho) \neq Cen(\rho)\). Then \(\rho = \{y_1, y_2, \ldots y_n \}\) with \(y_1 = y_2 =y_3= u\) and \(\{\rho \} = \{u, u_i \}\) or \(\{u, v \}\) and \(L(\rho) =\{u \}\). Therefore, \(\pi\rho\) must be of the form \((z_1,z_2,\dots, z_n )\) with \(z_1=z_2=z_3=u, \{ \pi\rho \} \subseteq \{u, v, u_1, u_2, \ldots, u_n \}\). Hence, \(L(\pi\rho) =\{u \}\). Hence, (Pre-C) is satisfied.
Let \(L(\rho) =Cen(\rho)\). Since \(L(\pi) \cap L(\rho) \neq \emptyset\), \(\rho\) can be of the following types: type \((1)\), type \((2)\), type \((3)\), type \((4)\) or type \((6)\). If \(\rho\) is of type \((1)\), then \(\{\rho \}\) is equal to \(\{u\}\) or \(\{u, u_i\}\) or \(\{u,v \}\). Hence, \(L(\pi\rho) = \{u\}\). If \(\rho\) is of type \((2)\), then \(\pi\rho \subseteq \{u, v, u_1, u_2, \ldots, u_n \}\). Hence, \(L(\pi\rho) = \{u \}\). If \(\rho\) is of type \((3)\), then \(L(\pi\rho) \subseteq L(\rho)\). If \(\rho\) is of type \((4)\), then \(\pi\rho\) is of type \((4)\), with \(L(\pi\rho) =L(\rho) =\{u, v \}\). If \(\rho\) is of type \((6)\), then either \(\pi\rho\) is of type \((6)\) with \(\{\pi \} \subseteq \{\rho \}\) or \(\pi\rho\) is of type \((3)\) with \(\{\pi \} = \{u, u_i \}\) and \(u_i \notin \{\rho \}\). In the first case \(L(\pi\rho) = L(\rho)\) and in the second case, \(L(\pi\rho) \subseteq L(\rho)\). Hence, (Pre-C) is satisfied in all cases.
Subcase iii. Let \(L(\rho) \neq Cen(\rho)\).
Therefore, \(\rho = (x_1, x_2, \ldots, x_n)\) with \(x_1=x_2=x_3=u, \{ \rho \} = \{u, u_i \}\) or \(\{u, v \}\) and \(L(\rho) = \{u \}\).Then we consider the two cases: \(L(\pi) \neq Cen(\pi)\) and \(L(\pi) = Cen(\pi)\) .
If \(L(\pi) \neq Cen(\pi)\), then \(\pi\rho\) must be of the form \((x_1, x_2, \ldots, x_n)\) with \(x_1 = x_2 = u, \{\pi\rho \} \subseteq \{u, v, u_1, u_2, \ldots, u_n \}\). Therefore, \(L(\pi\rho) = \{u \}\). Thus, \(L(\rho) = \{u\} =L(\pi\rho)\). Thus, (Pre-C) is satisfied.
If \(L(\pi) = Cen(\pi),\) then \(\pi \neq (x_1, x_2, \ldots, x_n)\) with \(x_1 = x_2 = u, \{\pi \} = \{u, u_i \}\) or \(\{u, v \}\). Therefore, in this case \(L(\pi\rho) =Cen(\pi\rho)\). Since \(L(\rho) = \{u \}\) and \(L(\pi) \cap L(\rho) \neq \emptyset\), \(u \in L(\pi)\). Hence, \(\pi\) can be of type \((1)\), type \((2)\), type \((3)\), type \((4)\) or type \((6)\). As in Case 2, here (Pre-C) is satisfied. ◻
Example 4.2(Not \((M)\)).Consider a consensus function \(L\) defined on book graph \(B_n\) as follows \[L(\pi) =\begin{cases} \{u \} & if ~ \{\pi \} = \{u_i, v \}, i=1,2,\ldots n, \\ Cen(\pi) & otherwise. \end{cases}\]
Claim 3. \(L\) satisfies \((PI)\), (Pre-C), \((CC)\) and \((TC)\), but not \((M)\).
Proof. Let \(\pi =(u_1, v)\). Then \(L(\pi) = \{u\}\), but \(Mid(u_1, v) = \{u, v_1 \}\). Hence, \((M)\) is violated. For any profiles \(\pi\) and \(\rho\) with \(\{\pi \} =\{\rho \}\), \(L(\pi) = L(\rho)\). Thus, \((PI)\) is satisfied. For profiles of length three \(L(\pi) =Cen(\pi)\). Thus \((TC)\) is satisfied. Since on \(B_n\), \(Cen\) satisfies \((CC)\), \((CC)\) is satisfied. We now prove that \(L\) satisfies (Pre-C).
Let \(S= \{ \{u_i, v \} , i= 1, 2, \ldots, n \}\). Let \(\pi\) and \(\rho\) be two profiles with \(L(\pi) \cap L(\rho) \neq \emptyset\). Then we have the following cases:
Case 1. Let \(\{\pi \} \in S\) and \(\{\rho \} \in S\).
Then \(\{ \pi\rho \} \in S\) if and only if \(\{\pi \} =\{\rho \}\). Therefore, \(L(\pi) =\{u\} = L(\rho)\). If \(\{\pi\rho\} \notin S\) then \(\pi\rho\) is of type \((2)\). Then \(L(\pi\rho) = Cen(\pi\rho) = \{u \}\).
Case 2. \(\{\pi \} \in S\) and \(\{\rho \} \notin S\).
Then \(L(\pi) = \{u \}\). If \(\{\pi\rho \} \in S\) , then \(\{\pi \} = \{\rho \} = \{\pi\rho \}\). If \(\{\pi\rho\} \notin S\), then since \(L(\pi) \cap L(\rho) \neq \emptyset, \rho\) can be of type \((1)\), type \((2)\), type \((3)\), type \((4)\) or type \((6)\). If \(\rho\) is of type \((1)\), then \(\{\rho \}\) is equal to \(\{u_i, u\}\) or \(\{u, v\}\) or \(\{u\}\). In this case, \(\{\pi\rho \} = \{u, u_i, v\}\) or \(\{\pi\rho \} = \{u, u_i, u_j,v\}\). Thus, \(L(\pi\rho) = \{u\} = L(\pi)\). Hence, \(L(\pi) \cap L(\rho)=\{u\}= L(\pi\rho)\subseteq L(\pi)\cup L(\rho)\). So, (Pre-C) is satisfied. If \(\rho\) is of type \((2)\) and \(\rho \notin S\), \(\pi\rho\) is also of type \((2)\), with \(L(\rho) =L(\pi\rho) = \{u \}\). Then \(L(\pi) \cap L(\rho) = \{u\} \neq \emptyset\). Since \(L(\pi) = L(\rho) =L(\pi\rho) =\{u\}\), (Pre-C) If \(\rho\) is of type \((3)\), then \(\pi\rho\) can be of type \((3)\) or type \((4)\) with \(\{u, v \} \subseteq L(\pi\rho) \subseteq L(\rho)\). Hence, \(L(\pi) \cap L(\rho) =\{u \} \subseteq L(\pi\rho) \subseteq L(\pi) \cup L(\rho)\). If \(\rho\) is of type \((4)\), then \(\pi\rho\) is of type \((4)\), \(L(\pi) \cap L(\rho) =\{u \},L(\pi\rho) = \{u, v \} =L(\rho)\). If \(\{\rho \}\) is of type \((6)\), then \(\pi\rho\) is of type \((3)\) with \(\{u, v\} \subseteq L(\pi\rho) \subseteq L(\rho)\) or \(\pi\rho\) is of type \((6)\) with \(\{\pi\rho \} =\{\rho \}\). If \(\pi\rho\) is of type \((3)\), \(L(\pi) \cap L(\rho) =\{u\} \neq \emptyset\) and \(L(\pi) \cap L(\rho) =\{u\} \subseteq \{u, v\} \subseteq L(\pi\rho) \subseteq L(\rho)=L(\pi) \cup L(\rho)\). On the other hand if \(\pi\rho\) is of type \((6)\), then \(L(\pi\rho) = L(\rho) = \{u_i, v_i, u, v\}\). Hence, \(L(\pi) \cap L(\rho) =\{u\} \neq \emptyset\) and since \(L(\rho) = L(\pi\rho)\), (Pre-C) is satisfied. Thus, in all cases (Pre-C) is satisfied.
Case 3. \(\{\pi\} \notin S\) and \(\{\rho \} \in S\). Similarly as in Case 2, (Pre-C) is satisfied.
Case 4. \(\{\pi \} \notin S\) and \(\{\rho \} \notin S\). Then \(\{\pi\rho\} \notin S\), for if \(\pi\rho \in S\), then \(L(\pi) \cap L(\rho) =\emptyset\). Therefore, \(L(\pi) = Cen(\pi),L(\rho) = Cen(\rho)\) and \(L(\pi\rho) = Cen(\pi\rho)\). Since, \(Cen\) satisfies (Pre-C), (Pre-C) is satisfied. ◻
Example 4.3 (Not \((Pre-C)\)).Let \(L\) be a consensus function defined on book graph \(B_3\). For any profile \(\pi\), define \(L\) as follows \[L(\pi) = \begin{cases} \{u, v \} & if ~ \{\pi \} = \{u_i\} \cup Y,\\ Cen(\pi) & otherwise. \end{cases}\]
Since \(Cen\) satisfies \((M), (CC)\) and \((TC)\) on \(B_n\), and \(L=Cen\), for all profiles \(\pi\) with \(\{\pi \} \neq \{u_i\} \cup Y\), \(L\) satisfies \((M), (CC)\) and \((TC)\). From the defintion of \(L\), for any profiles \(\pi\) and \(\rho\) with \(\{\pi \} =\{\rho \}\), \(L(\pi) = L(\rho)\). Thus, \((PI)\) is satisfied. Let \(\{\pi \} =\{u_1 \} \cup Y\) and \(\{\rho \} = \{u_1, u \}\). Therefore, \(L(\pi) = \{u_1 \},L(\rho) = Cen(\rho) = \{u_1, u \}, L(\pi\rho) =L(\{u, u_1\} \cup Y) = Cen(\{u, u_1\} \cup Y) = \{u, v, v_1 \}\). Hence, \(L(\pi) \cap L(\rho) = \{u_1\} \neq \emptyset\). But \(L(\pi) \cap L(\rho) =\{u_1\} \nsubseteq \{u, v, v_1\} = L(\pi\rho)\). Thus, (Pre-C) is violated.
Example 4.4(Not \((CC)\)).Let \(L\) be a consensus function defined on book graph \(B_n, n \geq 3\) as follows\[L(\pi) = \begin{cases} \{u_i, v_i \} & if ~ \{ \pi\} = \{u, v, u_i, v_i \}, \text{ where } i=1,2, \dots, n; \;\text{profile of type (6) },\\ Cen(\pi) & otherwise. \end{cases}\]
Let \(\pi = (u, v, u_1, v_1)\). Then, \(L(u, v, u_1, v_1) = \{u_1, v_1 \} \neq \{u, v, u_1, v_1 \}\), hence \((CC)\) is violated. From Example 3.7, we can see that \(L\) satisfies \((PI), (M), (TC)\) and (Pre-C).
Example 4.5(Not \((TC)\) and \((Pre-C)\) ).Consider the consensus function \(L\) defined on the book graph \(B_3\) as follows:
\[L(\tau)=\begin{cases} \{u, v \} & if ~ \tau ~ \text{is of type}~ (3), |\{\tau \}|>2,\\ Cen(\tau) & otherwise. \end{cases}\]
Let \(\tau = (u_1, v_1, v_2)\). Then \(L(u_1, v_1, v_2) = \{u, v\}\), but \(Cen(u_1, v_1, v_2) = \{u, v, v_1\}\). Since \(L(\tau) \neq Cen(\tau)\), \((TC)\) is violated. Let \(\pi = (u_1, v_2)\) and \(\rho = (u_1, v_3)\). Then \(\pi\rho = (u_1, v_2, v_3)\). We have \(L(\pi) = \{u, v, v_1, u_2\}, L(\rho) = \{u, v, v_1, u_3\}\) and \(L(\pi\rho) = \{u, v\}\). Thus, \(L(\pi) \cap L(\rho) = \{u, v, v_1\} \neq \emptyset\). But \(L(\pi\rho) \nsubseteq L(\pi) \cup L(\rho)\). Thus, (Pre-C) is violated. For profiles of length two and length three, \(L(\pi) =Cen(\pi)\). Thus, \(L\) satisfies \((M)\) and \((TC)\). For profiles \(\pi\) and \(\rho\) with \(\{\pi \} = \{\rho \}\), \(L(\pi) =L(\rho)\). Thus, \((PI)\) is satisfied.
In this article, we attempted an axiomatic characterization of the center function on book graphs. The characterization was attained using a class-dependent axiom called the Cycle Consensus axiom (CC), along with the existing class-independent axioms \((PI), (TC), (M)\) and (Pre-C). The independence of the axioms \((PI), (CC), (M)\) and (Pre-C) used for the characterization was also proven. The independence of the \((TC)\) axiom, as well as the question of whether \((CC)\) axiom or a modified version of this axiom, will provide an axiomatic characterization of the center function on graph families, such as stacked book graphs and ladder graphs, which are structurally similar to book graphs, remain open problems in the study of the axiomatization of center functions.