Page 318 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 318
GROUPS, GRAPHS AND NETWORKS (MS-75)
Structure connectivity and substructure connectivity of the crossed cube
Dongqin Cheng, dqcheng168@jnu.edu.cn
Jinan University, China
Interconnection network is usually represented by a simple graph G. The structure connectivity
κ(G; H) and substructure connectivity κs(G; H) are the new proposed indicators to measure
network fault tolerance and reliability when the network fails with different structures. As a
variant of the popular network hypercube, the crossed cube is also a famous interconnection
network in parallel and distributed systems. In this paper, we establish the H-structure connec-
tivity of the n-dimensional crossed cube when H ∈ {K1,1, K1,3, Pk, C4} and 3 ≤ k ≤ n and H-
substructure connectivity of the n-dimensional crossed cube when H ∈ {K1,1, K1,3, Pk, Cm},
3 ≤ k ≤ n and 4 ≤ m ≤ n.
Classifications of graphical m-semiregular representation of finite groups
Jiali Du, dujl@cumt.edu.cn
China University of Mining and Technology, China
A graph or digraph is called regular if each vertex has the same valency, or, the same out-valency
and the same in-valency, respectively. Recently, we extend the classical notion of digraphical
and graphical regular representation of a group. A (di)graphical m-semiregular representation
(respectively, GmSR and DmSR, for short) of a group G is a regular (di)graph whose auto-
morphism group is isomorphic to G and acts semiregularly on the vertex set with m orbits.
When m = 1, this definition agrees with the classical notion of GRR and DRR. Finite groups
admitting a D1SR were classified by Babai in 1980, and the analogue classification of finite
groups admitting a G1SR was completed by Godsil in 1981. Pivoting on these two results, we
classify finite groups admitting a GmSR or a DmSR (for arbitrary positive integers m) and also
do some work about bipartite (di)graphs.
Fault-tolerance of the data center networks
Rong-Xia Hao, rxhao@bjtu.edu.cn
Beijing Jiaotong University, China
The k-dimensional data center network with n-port switches, denoted by Dk,n, has been pro-
posed for data centers as a server centric network structure. The spanning trees of a graph
G are said to be the completely independent spanning trees (CISTs for short) if for any two
vertices x, y ∈ V (G), the paths joining x and y on the trees have neither vertex nor edge in
common, except x and y.
In this talk, some properties about Dk,n such as vertex-pancyclicity and the existence of two
completely independent spanning trees are given. Furthermore, we consider fault-tolerance and
prove that Dk,n is conditional (2n + 2k − 9)-edge-fault-tolerant Hamiltonian for any k ≥ 0 and
n ≥ 2 except k = 1 and n ≥ 6.
316
Structure connectivity and substructure connectivity of the crossed cube
Dongqin Cheng, dqcheng168@jnu.edu.cn
Jinan University, China
Interconnection network is usually represented by a simple graph G. The structure connectivity
κ(G; H) and substructure connectivity κs(G; H) are the new proposed indicators to measure
network fault tolerance and reliability when the network fails with different structures. As a
variant of the popular network hypercube, the crossed cube is also a famous interconnection
network in parallel and distributed systems. In this paper, we establish the H-structure connec-
tivity of the n-dimensional crossed cube when H ∈ {K1,1, K1,3, Pk, C4} and 3 ≤ k ≤ n and H-
substructure connectivity of the n-dimensional crossed cube when H ∈ {K1,1, K1,3, Pk, Cm},
3 ≤ k ≤ n and 4 ≤ m ≤ n.
Classifications of graphical m-semiregular representation of finite groups
Jiali Du, dujl@cumt.edu.cn
China University of Mining and Technology, China
A graph or digraph is called regular if each vertex has the same valency, or, the same out-valency
and the same in-valency, respectively. Recently, we extend the classical notion of digraphical
and graphical regular representation of a group. A (di)graphical m-semiregular representation
(respectively, GmSR and DmSR, for short) of a group G is a regular (di)graph whose auto-
morphism group is isomorphic to G and acts semiregularly on the vertex set with m orbits.
When m = 1, this definition agrees with the classical notion of GRR and DRR. Finite groups
admitting a D1SR were classified by Babai in 1980, and the analogue classification of finite
groups admitting a G1SR was completed by Godsil in 1981. Pivoting on these two results, we
classify finite groups admitting a GmSR or a DmSR (for arbitrary positive integers m) and also
do some work about bipartite (di)graphs.
Fault-tolerance of the data center networks
Rong-Xia Hao, rxhao@bjtu.edu.cn
Beijing Jiaotong University, China
The k-dimensional data center network with n-port switches, denoted by Dk,n, has been pro-
posed for data centers as a server centric network structure. The spanning trees of a graph
G are said to be the completely independent spanning trees (CISTs for short) if for any two
vertices x, y ∈ V (G), the paths joining x and y on the trees have neither vertex nor edge in
common, except x and y.
In this talk, some properties about Dk,n such as vertex-pancyclicity and the existence of two
completely independent spanning trees are given. Furthermore, we consider fault-tolerance and
prove that Dk,n is conditional (2n + 2k − 9)-edge-fault-tolerant Hamiltonian for any k ≥ 0 and
n ≥ 2 except k = 1 and n ≥ 6.
316
