Search

Let Γ be a graph with vertex set V, and let a, b be nonnegative integers. An (a, b)-regular set in Γ is a nonempty proper subset D of V such that every vertex in D has exactly a neighbours in D and every vertex in V \ D has exactly b neighbours in D. In particular, a (1, 1)-regular set is called a total perfect code. Let G be a finite group and S a square-free subset of G closed under conjugation. The Cayley sum graph CayS (G , S) of G is the graph with vertex set G such that two vertices x, y are adjacent if and only if x y ∈ S . A subset (respectively, subgroup) D of G is called an (a, b)-regular set (respectively, subgroup (a, b)-regular set) of G if there exists a Cayley sum graph of G which admits D as an (a, b)-regular set. We obtain two necessary and sufficient conditions for a subgroup of a finite group G to be a total perfect code in a Cayley sum graph of G. We also obtain two necessary and sufficient conditions for a subgroup of a finite abelian group G to be a total perfect code of G. We classify finite abelian groups whose all non-trivial subgroups of even order are total perfect codes of the group, and as a corollary we obtain that a finite abelian group has the property that every non-trivial subgroup is a total perfect code if and only if it is isomorphic to an elementary abelian 2-group. We prove that, for a subgroup H of a finite abelian group G and any pair of positive integers (a, b) within certain ranges depending on H, H is an (a, b)-regular set of G if and only if it is a total perfect code of G. Finally, we give a classification of subgroup total perfect codes of a cyclic group, a dihedral group and a generalized quaternion group. [ABSTRACT FROM AUTHOR]

We prove that every regular graph of valency at least four whose automorphism group contains a nilpotent subgroup acting transitively on the vertex set admits a nowhere-zero 3-flow. [ABSTRACT FROM AUTHOR]

Let Γ = (V , E) be a graph and a, b nonnegative integers. An (a, b)-regular set in Γ is a nonempty proper subset D of V such that every vertex in D has exactly a neighbours in D and every vertex in V \ D has exactly b neighbours in D. A (0, 1)-regular set is called a perfect code, an efficient dominating set, or an independent perfect dominating set. A subset D of a group G is called an (a, b)-regular set of G if it is an (a, b)-regular set in some Cayley graph of G, and an (a, b)-regular set in a Cayley graph of G is called a subgroup (a, b)-regular set if it is also a subgroup of G. In this paper, we study (a, b)-regular sets in Cayley graphs with a focus on (0, k)-regular sets, where k ≥ 1 is an integer. Among other things, we determine when a non-trivial proper normal subgroup of a group is a (0, k)-regular set of the group. We also determine all subgroup (0, k)-regular sets of dihedral groups and generalized quaternion groups. We obtain necessary and sufficient conditions for a hypercube or the Cartesian product of n copies of the cycle of length p to admit (0, k)-regular sets, where p is an odd prime. Our results generalize several known results from perfect codes to (0, k)-regular sets. [ABSTRACT FROM AUTHOR]

The fact that the adjacency matrix of every finite graph is diagonalizable plays a fundamental role in spectral graph theory. Since this fact does not hold in general for digraphs, it is natural to ask whether it holds for digraphs with certain level of symmetry. Interest in this question dates back to the early 1980 s, when P. J. Cameron asked for the existence of arc-transitive digraphs with non-diagonalizable adjacency matrix. This was answered in the affirmative by Babai (J Graph Theory 9:363–370, 1985). Then Babai posed the open problems of constructing a 2-arc-transitive digraph and a vertex-primitive digraph whose adjacency matrices are not diagonalizable. In this paper, we solve Babai's problems by constructing an infinite family of s-arc-transitive digraphs for each integer s ≥ 2 , and an infinite family of vertex-primitive digraphs, both of whose adjacency matrices are non-diagonalizable. [ABSTRACT FROM AUTHOR]

A graphical regular representation of a group G is a Cayley graph of G whose full automorphism group is equal to the right regular permutation representation of G. In this paper, we prove that for Ree groups Ree (q) with q > 3, with probability tending to 1 as q → ∞ , a random involution y together with a fixed element x with order q – 1 gives rise to a cubic graphical regular representation of Ree (q) . A similar result involving a fixed element with order q + 3 q + 1 is also proved with the help of certain properties of Ree (q) given in [Leemans, D. Liebeck, M. W. (2017). Chiral polyhedra and finite simple groups. Bull. London Math. Soc. 49: 581–592]. [ABSTRACT FROM AUTHOR]

In a graph Γ with vertex set V, a subset C of V is called an (a, b)-regular set if every vertex in C has exactly a neighbors in C and every vertex in V \ C has exactly b neighbors in C, where a and b are nonnegative integers. In the literature, (0, 1)-regular sets are known as perfect codes and (1, 1)-regular sets are known as total perfect codes. In this paper, we prove that, for any finite group G, if a non-trivial normal subgroup H of G is a perfect code in some Cayley graph of G, then for any pair of integers a and b with 0 ⩽ a ⩽ | H | - 1 and 0 ⩽ b ⩽ | H | such that gcd (2 , | H | - 1) divides a, H is also an (a, b)-regular set in some Cayley graph of G depending on (a, b). A similar result involving total perfect codes is also proved in the paper. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

A graph $\Gamma $ is called $(G, s)$ -arc-transitive if $G \le \text{Aut} (\Gamma)$ is transitive on the set of vertices of $\Gamma $ and the set of s-arcs of $\Gamma $ , where for an integer $s \ge 1$ an s-arc of $\Gamma $ is a sequence of $s+1$ vertices $(v_0,v_1,\ldots ,v_s)$ of $\Gamma $ such that $v_{i-1}$ and $v_i$ are adjacent for $1 \le i \le s$ and $v_{i-1}\ne v_{i+1}$ for $1 \le i \le s-1$. A graph $\Gamma $ is called 2-transitive if it is $(\text{Aut} (\Gamma), 2)$ -arc-transitive but not $(\text{Aut} (\Gamma), 3)$ -arc-transitive. A Cayley graph $\Gamma $ of a group G is called normal if G is normal in $\text{Aut} (\Gamma)$ and nonnormal otherwise. Fang et al. ['On edge transitive Cayley graphs of valency four', European J. Combin.25 (2004), 1103–1116] proved that if $\Gamma $ is a tetravalent 2-transitive Cayley graph of a finite simple group G, then either $\Gamma $ is normal or G is one of the groups $\text{PSL}_2(11)$ , ${\rm M} _{11}$ , $\text{M} _{23}$ and $A_{11}$. However, it was unknown whether $\Gamma $ is normal when G is one of these four groups. We answer this question by proving that among these four groups only $\text{M} _{11}$ produces connected tetravalent 2-transitive nonnormal Cayley graphs. We prove further that there are exactly two such graphs which are nonisomorphic and both are determined in the paper. As a consequence, the automorphism group of any connected tetravalent 2-transitive Cayley graph of any finite simple group is determined. [ABSTRACT FROM AUTHOR]

The canonical double cover D(Γ) of a graph Γ is the direct product of Γ and K2. If Aut(D(Γ))≅Aut(Γ)×Z2 then Γ is called stable; otherwise Γ is called unstable. An unstable graph is said to be nontrivially unstable if it is connected, non‐bipartite and no two vertices have the same neighborhood. In 2008 Wilson conjectured that, if the generalized Petersen graph GP(n,k) is nontrivially unstable, then both n and k are even, and either n/2 is odd and k2≡±1(mod n/2), or n=4k. In this note we prove that this conjecture is true. At the same time we determine all possible isomorphisms among the generalized Petersen graphs, the canonical double covers of the generalized Petersen graphs, and the double generalized Petersen graphs. Based on these we completely determine the full automorphism group of the canonical double cover of GP(n,k) for any pair of integers n,k with 1⩽k

Let Γ be a graph with vertex set V ( Γ ). A subset C of V ( Γ ) is called a perfect code in Γ if C is an independent set of Γand every vertex in V ( Γ ) \ 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. [ABSTRACT FROM AUTHOR]

We derive upper and lower bounds for the vertex-isoperimetric number of the incidence graphs of unitals and determine its order of magnitude. In the case when a unital contains sufficiently large arcs, these bounds agree and give rise to the precise value of this parameter. In particular, we obtain the exact value of the vertex-isoperimetric number of the incidence graphs of classical unitals and a certain subfamily of BM-unitals. In the case when the maximum size of arcs in the unital is relatively small, we obtain an upper bound for this parameter in terms of the vertex-isoperimetric number of the incidence graph. We also determine the exact value of the vertex-isoperimetric number of the non-incidence graph of any unital. [ABSTRACT FROM AUTHOR]

We prove the existence and give constructions of a $(p(k)-1)$ -fold perfect resolvable $(v,k,1)$ -Mendelsohn design for any integers $v>k\geq 2$ with $v\equiv 1\hspace{0.2em}{\rm mod}\hspace{0.2em}\,k$ such that there exists a finite Frobenius group whose kernel $K$ has order $v$ and whose complement contains an element $\unicode[STIX]{x1D719}$ of order $k$ , where $p(k)$ is the least prime factor of $k$. Such a design admits $K\rtimes \langle \unicode[STIX]{x1D719}\rangle$ as a group of automorphisms and is perfect when $k$ is a prime. As an application we prove that for any integer $v=p_{1}^{e_{1}}\cdots p_{t}^{e_{t}}\geq 3$ in prime factorisation and any prime $k$ dividing $p_{i}^{e_{i}}-1$ for $1\leq i\leq t$ , there exists a resolvable perfect $(v,k,1)$ -Mendelsohn design that admits a Frobenius group as a group of automorphisms. We also prove that, if $k$ is even and divides $p_{i}-1$ for $1\leq i\leq t$ , then there are at least $\unicode[STIX]{x1D711}(k)^{t}$ resolvable $(v,k,1)$ -Mendelsohn designs that admit a Frobenius group as a group of automorphisms, where $\unicode[STIX]{x1D711}$ is Euler’s totient function. [ABSTRACT FROM AUTHOR]

Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers [ABSTRACT FROM AUTHOR]

A total perfect code in a graph $$\Gamma $$ is a subset C of $$V(\Gamma )$$ such that every vertex of $$\Gamma $$ is adjacent to exactly one vertex in C. We give necessary and sufficient conditions for a conjugation-closed subset of a group to be a total perfect code in a Cayley graph of the group. As an application we show that a Cayley graph on an elementary abelian 2-group admits a total perfect code if and only if its degree is a power of 2. We also obtain necessary conditions for a Cayley graph of a group with connection set closed under conjugation to admit a total perfect code. [ABSTRACT FROM AUTHOR]

The generalized k-connectivity $$\kappa _{k}(G)$$ and the generalized k-edge-connectivity $$\lambda _k(G)$$ of a graph G, also known as the tree connectivities, were introduced by Hager (J Comb Theory Ser B 38:179-189, 1985) and Li et al. (Discret Math Theor Comput Sci 14:43-54, 2012), respectively. In this paper, we study these invariants for Cayley graphs on Abelian groups with degree 3 or 4. When G is cubic, we prove $$\kappa _k(G) = \lambda _k(G) = 2$$ for $$3\le k\le 6$$ and $$\kappa _k(G) = \lambda _k(G) = 1$$ for $$7\le k\le n$$ . When G has degree 4, we obtain $$\kappa _{3}(G)=\lambda _3(G)=3$$ , $$\lambda _k(G) = 2$$ and $$\kappa _k(G)\le 2$$ for $$k\ge 8$$ , and $$\kappa _k(G) = 2$$ for $$k=n-1,n$$ . [ABSTRACT FROM AUTHOR]

Given a graph G with n vertices and an Abelian group A of order n, an A-distance antimagic labelling of G is a bijection from V ( G) to A such that the vertices of G have pairwise distinct weights, where the weight of a vertex is the sum (under the operation of A) of the labels assigned to its neighbours. An A-distance magic labelling of G is a bijection from V ( G) to A such that the weights of all vertices of G are equal to the same element of A. In this paper we study these new labellings under a general setting with a focus on product graphs. We prove among other things several general results on group antimagic or magic labellings for Cartesian, direct and strong products of graphs. As applications we obtain several families of graphs admitting group distance antimagic or magic labellings with respect to elementary Abelian groups, cyclic groups or direct products of such groups. [ABSTRACT FROM AUTHOR]

The orbit problem is at the heart of symmetry reduction methods for model checking concurrent systems. It asks whether two given configurations in a concurrent system (represented as finite strings over some finite alphabet) are in the same orbit with respect to a given finite permutation group (represented by their generators) acting on this set of configurations by permuting indices. It is known that the problem is in general as hard as the graph isomorphism problem, whose precise complexity (whether it is solvable in polynomial-time) is a long-standing open problem. In this paper, we consider the restriction of the orbit problem when the permutation group is cyclic (i.e. generated by a single permutation), an important restriction of the problem. It is known that this subproblem is solvable in polynomial-time. Our main result is a linear-time algorithm for this subproblem. [ABSTRACT FROM AUTHOR]

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G-symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G-symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given. [ABSTRACT FROM AUTHOR]

This paper establishes connections between the structure of a semigroup and the minimum spans of distance labellings of its Cayley graphs. We show that certain general restrictions on the minimum spans are equivalent to the semigroup being combinatorial, and that other restrictions are equivalent to the semigroup being a right zero band. We obtain a description of the structure of all semigroups S and their subsets C such that $$\,{\mathrm {Cay}}(S,C)$$ is a disjoint union of complete graphs, and show that this description is also equivalent to several restrictions on the minimum span of $$\,{\mathrm {Cay}}(S,C)$$ . We then describe all graphs with minimum spans satisfying the same restrictions, and give examples to show that a fairly straightforward upper bound for the minimum spans of the underlying undirected graphs of Cayley graphs turns out to be sharp even for the class of combinatorial semigroups. [ABSTRACT FROM AUTHOR]

A preface for the September 2017 issue of the journal "Journal of Interconnection Networks" is presented.

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple ( v, u, x, y) of vertices such that both ( v, u, x) and ( u, x, y) are paths of length two. The 3-arc graph of a graph G is defined to have vertices the arcs of G such that two arcs uv, xy are adjacent if and only if ( v, u, x, y) is a 3-arc of G. We prove that any connected 3-arc graph is hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are hamiltonian. As a corollary we obtain that any vertex-transitive graph which is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three must be hamiltonian. This confirms the conjecture, for this family of vertex-transitive graphs, that all vertex-transitive graphs with finitely many exceptions are hamiltonian. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs. [ABSTRACT FROM AUTHOR]

Given simple graphsand, the neighbourhood corona ofand, denoted, is the graph obtained by taking one copy ofandcopies of, and joining the neighbours of theth vertex ofto every vertex in theth copy of. In this paper we determine the adjacency spectrum offor arbitraryand, and the Laplacian spectrum and signless Laplacian spectrum offor regularand arbitrary, in terms of the corresponding spectrum ofand. The results on the adjacency and signless Laplacian spectra enable us to construct new pairs of adjacency cospectral and signless Laplacian cospectral graphs. As applications of the results on the Laplacian spectra, we give constructions of new families of expander graphs from known ones by using neighbourhood coronae. [ABSTRACT FROM PUBLISHER]

A graph $\Gamma $ is $G$-symmetric if $\Gamma $ admits $G$ as a group of automorphisms acting transitively on the set of vertices and the set of arcs of $\Gamma $, where an arc is an ordered pair of adjacent vertices. In the case when $G$ is imprimitive on $V(\Gamma )$, namely when $V(\Gamma )$ admits a nontrivial $G$-invariant partition ${\mathcal{B}}$, the quotient graph $\Gamma _{\mathcal{B}}$ of $\Gamma $ with respect to ${\mathcal{B}}$ is always $G$-symmetric and sometimes even $(G, 2)$-arc transitive. (A $G$-symmetric graph is $(G, 2)$-arc transitive if $G$ is transitive on the set of oriented paths of length two.) In this paper we obtain necessary conditions for $\Gamma _{{\mathcal{B}}}$ to be $(G, 2)$-arc transitive (regardless of whether $\Gamma $ is $(G, 2)$-arc transitive) in the case when $v-k$ is an odd prime $p$, where $v$ is the block size of ${\mathcal{B}}$ and $k$ is the number of vertices in a block having neighbours in a fixed adjacent block. These conditions are given in terms of $v, k$ and two other parameters with respect to $(\Gamma , {\mathcal{B}})$ together with a certain 2-point transitive block design induced by $(\Gamma , {\mathcal{B}})$. We prove further that if $p=3$ or $5$ then these necessary conditions are essentially sufficient for $\Gamma _{{\mathcal{B}}}$ to be $(G, 2)$-arc transitive. [ABSTRACT FROM AUTHOR]

Unitary graphs are arc-transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc-transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power [ABSTRACT FROM AUTHOR]

A finite graph Γ is called G-symmetric if G is a group of automorphisms of Γ which is transitive on the set of ordered pairs of adjacent vertices of Γ. We study a family of symmetric graphs, called the unitary graphs, whose vertices are flags of the Hermitian unital and whose adjacency relations are determined by certain elements of the underlying finite fields. Such graphs admit the unitary groups as groups of automorphisms, and play a significant role in the classification of a family of symmetric graphs with complete quotients such that an associated incidence structure is a doubly point-transitive linear space. We give this classification in the paper and also investigate combinatorial properties of the unitary graphs. [ABSTRACT FROM AUTHOR]

A k- L(2,1)-labelling of a graph G is a mapping f: V( G)→{0,1,2,..., k} such that | f( u)− f( v)|≥2 if uv∈ E( G) and f( u)≠ f( v) if u, v are distance two apart. The smallest positive integer k such that G admits a k- L(2,1)-labelling is called the λ-number of G. In this paper we study this quantity for cubic Cayley graphs (other than the prism graphs) on dihedral groups, which are called brick product graphs or honeycomb toroidal graphs. We prove that the λ-number of such a graph is between 5 and 7, and moreover we give a characterisation of such graphs with λ-number 5. [ABSTRACT FROM AUTHOR]

Let Г be a G-symmetric graph admitting a nontrivial G-invariant partition $${\cal B}$$. Let Г $$_{\cal B}$$ be the quotient graph of Г with respect to $${\cal B}$$. For each block B ∊ $${\cal B}$$, the setwise stabiliser G B of B in G induces natural actions on B and on the neighbourhood Г $$_{\cal B}$$( B) of B in Г $$_{\cal B}$$. Let G( B) and G[ B] be respectively the kernels of these actions. In this paper we study certain “local actions" induced by G( B) and G[ B], such as the action of G[ B] on B and the action of G( B) on Г $$_{\cal B}$$( B), and their influence on the structure of Г. [ABSTRACT FROM AUTHOR]

In the Weighted Ring Arc-Loading Problem with Integer Splitting, we are given a set of communication requests each associated with a non-negative integer weight. The problem is to find a routing scheme such that the maximum load on arcs of the ring is minimized, subject to that the weight of each request may be split into two integral parts routed in two directions around the ring, where the load of an arc is the sum of parts routed through the arc. A pseudo-polynomial algorithm for this problem is implied by a result in [C. Wilfong and P. Winkler, Ring routing and wavelength translation, Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, 1998, 333-341]. By refining the rounding technique developed in the same paper, we prove that the problem can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

A Cayley graph or digraph Cay( G, S) is called a CI-graph of G if, for any T⊂ G, Cay( G, S)≅Cay( G, T) if and only if Sσ= T for some σ∈Aut( G). The aim of this paper is to characterize finite abelian groups for which all minimal Cayley graphs and digraphs are CI-graphs. [ABSTRACT FROM AUTHOR]

Let f be an integer-valued function defined on the vertex set V( G) of a graph G. A subset D of V( G) is an f-dominating set if each vertex x outside D is adjacent to at least f( x) vertices in D. The minimum number of vertices in an f-dominating set is defined to be the f-domination number, denoted by γ f( G). In a similar way one can define the connected and total f-domination numbers γ c, f( G) and γ t, f( G). If f( x) = 1 for all vertices x, then these are the ordinary domination number, connected domination number and total domination number of G, respectively. In this paper we prove some inequalities involving γ f( G), γ c, f( G), γ t, f( G) and the independence domination number i( G). In particular, several known results are generalized. [ABSTRACT FROM AUTHOR]

Let G be a graph with order p, size q and component number ω. For each i between p − ω and q, let $$C_i (G)$$ be the family of spanning i-edge subgraphs of G with exactly ω components. For an integer-valued graphical invariant φ if H → H′ is an adjacent edge transformation (AET) implies |φ(H)-φ(H')|≤1 then φ is said to be continuous with respect to AET. Similarly define the continuity of φ with respect to simple edge transformation (SET). Let Mj(φ) and mj(φ) be the invariants defined by $$M_j (\varphi )(H) = \mathop {\max }\limits_{T \in C_j (H)} \varphi (T),m_j (\varphi )(H) = \mathop {\min }\limits_{T \in C_j (H)} \varphi (T)$$ . It is proved that both Mp−ω(φ) and mp−ω(φ;) interpolate over $$\mathcal{C}_i (G),p - \omega \leqslant i \leqslant q$$ , if φ is continuous with respect to AET, and that Mj(φ) and mj(φ) interpolate over $$\mathcal{C}_i (G),p - \omega \leqslant j \leqslant i \leqslant q$$ , if φ is continuous with respect to SET. In this way a lot of known interpolation results, including a theorem due to Schuster etc., are generalized. [ABSTRACT FROM AUTHOR]

The article discusses various papers published in this issue including one on graphs of ideals of commutative ring, one on Cayley graphs and one on Laplacian spectra of graphs.