Abstract A perfect code in a graph $$\Gamma = (V, E)$$ Γ = ( V , E ) is a subset C of V such that no two vertices in C are adjacent and every vertex in $$V \setminus C$$ V \ C is adjacent to exactly one vertex in C . A total perfect code in $$\Gamma $$ Γ is a subset C of V such that every vertex of $$\Gamma $$ Γ is adjacent to exactly one vertex in C . In this paper we prove several results on perfect codes and total perfect codes in Cayley graphs of finite abelian groups.

Let $V$ be an $n$-dimensional vector space over a finite field $\mathbb{F}_q$. In this paper we describe the structure of maximal nontrivial $t$-intersecting families of $k$-dimensional subspaces of $V$ with large size. We also determine the nontrivial $t$-intersecting families with maximum size. In the special case when $t=1$ our result gives rise to the well-known Hilton--Milner theorem for vector spaces.

Blowfish privacy is a recent generalisation of differential privacy that enables improved utility while maintaining privacy policies with semantic guarantees, a factor that has driven the popularity of differential privacy in computer science. This paper relates Blowfish privacy to an important measure of privacy loss of information channels from the communications theory community: min-entropy leakage. Symmetry in an input data neighbouring relation is central to known connections between differential privacy and min-entropy leakage. But while differential privacy exhibits strong symmetry, Blowfish neighbouring relations correspond to arbitrary simple graphs owing to the framework’s flexible privacy policies. To bound the min-entropy leakage of Blowfish-private mechanisms we organise our analysis over symmetrical partitions corresponding to orbits of graph automorphism groups. A construction meeting our bound with asymptotic equality demonstrates tightness.

An $L(h_1, h_2, \ldots, h_l)$-labelling of a graph $G$ is a mapping $\phi: V(G) \rightarrow \{0, 1, 2, \ldots\}$ such that for $1\le i\le l$ and each pair of vertices $u, v$ of $G$ at distance $i$, we have $|\phi(u) - \phi(v)| \geq h_i$. The span of $\phi$ is the difference between the largest and smallest labels assigned to the vertices of $G$ by $\phi$, and $\lambda_{h_1, h_2, \ldots, h_l}(G)$ is defined as the minimum span over all $L(h_1, h_2, \ldots, h_l)$-labellings of $G$. In this paper we study $\lambda_{h, 1, \ldots, 1}$ for Cartesian products of graphs, where $(h, 1, \ldots, 1)$ is an $l$-tuple with $l \ge 3$. We prove that, under certain natural conditions, the value of this and three related invariants on a graph $H$ which is the Cartesian product of $l$ graphs attain a common lower bound. In particular, the chromatic number of the $l$-th power of $H$ equals this lower bound plus one. We further obtain a sandwhich theorem which extends the result to a family of subgraphs of $H$ which contain a certain subgraph of $H$. All these results apply in particular to the class of Hamming graphs: if $q_1\ge \cdots \ge q_d\ge 2$ and $3\le l\le d$ then the Hamming graph $H=H_{q_1,q_2,\ldots ,q_d}$ satisfies $\lambda_{q_l,1,\ldots,1}(H) = q_1q_2\ldots q_l-1$ whenever $q_1q_2\ldots q_{l-1}>3(q_{l-1}+1)q_l\ldots q_d$. In particular, this settles a case of the open problem on the chromatic number of powers of the hypercubes.

Let $\Gamma$ be a graph with vertex set $V(\Gamma)$. A subset $C$ of $V(\Gamma)$ is called a perfect code in $\Gamma$ if $C$ is an independent set of $\Gamma$ and every vertex in $V(\Gamma)\setminus C$ is adjacent to exactly one vertex in $C$. A subset $C$ of a group $G$ is called a perfect code of $G$ if there exists a Cayley graph of $G$ which admits $C$ as a perfect code. A group $G$ is said to be code-perfect if every proper subgroup of $G$ is a perfect code of $G$. In this paper we prove that a group is code-perfect if and only if it has no elements of order 4. We also prove that a proper subgroup $H$ of an abelian group $G$ is a perfect code of $G$ if and only if the Sylow 2-subgroup of $H$ is a perfect code of the Sylow 2-subgroup of $G$. This reduces the problem of determining when a given subgroup of an abelian group is a perfect code to the case of abelian 2-groups. Finally, we determine all subgroup perfect codes in any generalized quaternion group.

Given a graph $\Gamma$, a subset $C$ of $V(\Gamma)$ is called a perfect code in $\Gamma$ if every vertex of $\Gamma$ is at distance no more than one to exactly one vertex in $C$, and a subset $C$ of $V(\Gamma)$ is called a total perfect code in $\Gamma$ if every vertex of $\Gamma$ is adjacent to exactly one vertex in $C$. In this paper we study perfect codes and total perfect codes in Cayley graphs, with a focus on the following themes: when a subgroup of a given group is a (total) perfect code in a Cayley graph of the group; and how to construct new (total) perfect codes in a Cayley graph from known ones using automorphisms of the underlying group. We prove several results around these questions.

Given integers n ≥ 7 and a, b, c with 1 ≤ a, b, c ≤ n − 1 such that a, n − a, b, n − b, c, n − c are pairwise distinct, the (undirected) triple-loop network TLn(a, b, c) is the degree-six graph with vertices 0, 1, 2,…,n − 1 such that each vertex x is adjacent to x ± a, x ± b, and x ± c, where the operation is modulo n. It is known that the maximum order of a connected triple-loop network of the form TLn(a, b, n − (a + b)) with given diameter d ≥ 2 is nd = 3d2 + 3d + 1, which is achieved by TL = TL(1, 3d+ 1, 3d2 − 1). In this article, we study the routing and gossiping problems for such optimal triple-loop networks under the store-and-forward, all-port, and full-duplex model, and prove that they admit “perfect” gossiping and routing schemes which exhibit many interesting features. Using a group-theoretic approach we develop for TL a method for systematically producing such optimal gossiping and routing schemes. Moreover, we determine the minimum gossip time, the edge- and arc-forwarding indices, and the minimal edge- and arc-forwarding indices of TL, and prove that our routing schemes are optimal with respect to these four indices simultaneously. As a key step towards these results, we prove that TL is a Frobenius graph on a Frobenius group with Frobenius kernel ℤ, and that TL is arc-transitive with respect to this Frobenius group. In addition, we show that TL admits complete rotations. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

We study a class of Cayley graphs as models for interconnection networks. With focus on efficient communication we prove that for any graph in the class there exists a gossiping protocol which exhibits attractive features, and, moreover, we give an algorithm for constructing such a protocol. In particular, these hold for two important subclasses of graphs, namely, Cayley graphs admitting a complete rotation and Frobenius graphs of a certain type. For such Frobenius graphs, we obtain the minimum gossip time and give an optimal gossiping protocol under which messages are transmitted along shortest paths and each arc is used exactly once at each time step. Moreover, for such Frobenius graphs we construct an all-to-all shortest path routing that is arc-transitive, edge- and arc-uniform, and optimal for the edge- and arc-forwarding indices simultaneously.

This paper presents a dynamic domination theory for fuzzy causal networks (FCN). There are three major contributions. First, we propose a new inference procedure based on dominating sets. Second, we introduce the concepts of dynamic and minimal dynamic dominating sets (DDS and MDDS) in an FCN. To reflect changes of dominance with time, we also introduce the concept of a dynamic dominating process (DDP) that has significant implications in many real-world problems. We pay a special attention to the minimal dynamic dominating process (MDDP) and develop rules for generating DDP and MDDP. Third, we investigate dynamic dominating sets with extended feedback, which we call effective dynamic dominating sets (EDDS), and related effective dynamic dominating process (EDDP). This study unveils a very important phenomenon in FCN: At any time t, either an EDDS exists or there is a dramatic change of the states of vertices. In the latter case we also identify the special structure of the sub-FCN induced by active vertices.

In this paper, we first propose a general framework for fuzzy causal networks (FCNs). Then, we study the dynamics and convergence of such general FCNs. We prove that any general FCN with constant weight matrix converges to a limit cycle or a static state, or the trajectory of the FCN is not repetitive. We also prove that under certain conditions a discrete state general FCN converges to its limit cycle or static state in O(n) steps, where n is the number of vertices of the FCN. This is in striking contrast with the exponential running time 2/sup n/, which is accepted widely for classic FCNs.

For given integers $j \ge k \ge 1$, an $L(j,k)$-labelling of a graph $\Ga$ is an assignment of labels---nonnegative integers---to the vertices of $\Ga$ such that adjacent vertices receive labels that differ by at least j, and vertices distance two apart receive labels that differ by at least k. The span of such a labelling is the difference between the largest and the smallest labels used, and the minimum span over all $L(j,k)$-labellings of $\Ga$ is denoted by $\l_{j,k}(\Ga)$. The minimum number of labels needed in an $L(j,k)$-labelling of $\Ga$ is independent of j and k, and is denoted by $\mu(\Ga)$. In this paper we introduce a general approach to $L(j,k)$-labelling Cayley graphs $\Ga$ over Abelian groups and deriving upper bounds for $\l_{j,k}(\Ga)$ and $\mu(\Ga)$. Using this approach we obtain upper bounds on $\l_{j,k}(\Ga)$ and $\mu(\Ga)$ for graphs $\Ga$ admitting a vertex-transitive Abelian group of automorphisms. Hypercubes $Q_d$ are examples of such graphs, and as consequences we obtain upper bounds for $\l_{j,k}(Q_d)$ and $\mu(Q_d)$. We also obtain the exact values of $\l_{j,k}(\Ga)$ ($2k \ge j \ge k$) and $\mu(\Ga)$ for some Hamming graphs $\Ga$. The result shows that, under certain arithmetic conditions, these two invariants rely only on k and the orders of the two largest complete graph factors of the Hamming graph.

In this paper, we introduce a decomposition theory for fuzzy cognitive maps (FCM). First, we partition the set of vertices of an FCM into blocks according to an equivalence relation, and by regarding these blocks as vertices we construct a quotient FCM. Second, each block induces a natural sectional FCM of the original FCM, which inherits the topological structure as well as the inference from the original FCM. In this way, we decompose the original FCM into a quotient FCM and some sectional FCM. As a result, the analysis of the original FCM is reduced to the analysis of the quotient and sectional FCM, which are often much smaller in size and complexity. Such a reduction is important in analyzing large-scale FCM. We also propose a causal algebra in the quotient FCM, which indicates that the effect that one vertex influences another in the quotient depends on the weights and states of the vertices along directed paths from the former to the latter. To illustrate the process involved, we apply our decomposition theory to university management networks. Finally, we discuss possible approaches to partitioning an FCM and major concerns in constructing quotient FCM. The results represented in this paper provide an effective framework for calculating and simplifying causal inference patterns in complicated real-world applications.