Article
Mathematics, Applied
Dongqin Cheng
Summary: This paper investigates a variant of the locally twisted cube called n-dimensional locally twisted cube and proves that its generalized 4-connectivity is n-1. This result is significant for evaluating the fault-tolerance of networks.
JOURNAL OF APPLIED MATHEMATICS AND COMPUTING
(2023)
Article
Computer Science, Hardware & Architecture
Ying-Ze Zhao, Xiang-Jun Li, Meijie Ma
Summary: Many interconnection networks in large-scale parallel computing have hierarchical and recursive structures. This paper focuses on the structures of the Crossed cube and the Mobius cube in the bijective connection networks, and determines their embedded connectivity using these structural properties.
JOURNAL OF SUPERCOMPUTING
(2022)
Article
Computer Science, Theory & Methods
Wantao Ning, Hao Li
Summary: This work investigates the h-edge connectivity of the exchanged crossed cube ECQ (s, t) and determines the minimum number of edges that need to be removed to disconnect the graph with no vertices of degree less than h.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Computer Science, Hardware & Architecture
Lina Ba, Yaxian Zhang, Heping Zhang
Summary: This paper investigates the P-t-structure connectivity and P-t-substructure connectivity of augmented k-ary n-cubes AQ(n,k). The minimum connectivity for these graphs is obtained under certain conditions.
Article
Computer Science, Theory & Methods
Shu-Li Zhao, Jou-Ming Chang
Summary: This paper investigates the generalized connectivity on the divide-and-swap cube DSCn, which has a nice hierarchical structure and plentiful properties. The result kappa 4(DSCn) = d is obtained by constructing d internally disjoint trees connecting any four arbitrary vertices of DSCn, where d = log2 n > 1. As a result, kappa 3(DSCn) = d.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Mathematics
Heqin Liu, Dongqin Cheng
Summary: The generalized connectivity is a new criterion for measuring the fault tolerance of networks. The n-dimensional crossed cube network CQ(n) is considered as an attractive alternative to hypercube network due to its many good properties. The results of the generalized 3-connectivity and generalized 4-connectivity of CQ(n) are kappa(3)(CQ(n)) = kappa(4)(CQ(n)) = n - 1, where n >= 2.
DISCUSSIONES MATHEMATICAE GRAPH THEORY
(2022)
Article
Multidisciplinary Sciences
Lantao You, Yuejuan Han, Jianfeng Jiang
Summary: The hypercube Q(n) is a highly symmetrical interconnection network. Variants of Q(n), such as the n-dimensional locally twisted cube LTQ(n), have been proposed to reduce its diameter. To further optimize the diameter, the n-dimensional folded locally twisted cube FLTQ(n) is introduced. Connectivity and super-connectivity are important indicators for fault tolerance and reliability of a network. In this paper, it is shown that the super-connectivity of FLTQ(n) is twice the connectivity.
Article
Computer Science, Hardware & Architecture
Chang Shu, Yan Wang, Jianxi Fan, Guijuan Wang
Summary: The fault-tolerant performance of a network, characterized by connectivity, is essential for its normal operation. Super H-connectivity and super H-*-connectivity provide a new metric, super structure fault-tolerance, to measure the network's fault-tolerance.
Article
Computer Science, Hardware & Architecture
Liqiong Xu, Shuming Zhou, Sun-Yuan Hsieh
Summary: This study investigates the $h$-extra edge connectivity of the 3-ary $n$-cube $Q_n<^>3$ and develops a recursive closed formula and efficient algorithm to determine the exact values of extra edge connectivity. The research also examines the $g$-component edge connectivity of the 3-ary $n$-cube $Q_n<^>3$ for certain values of $g$ when $n\geq 6$.
IEEE TRANSACTIONS ON RELIABILITY
(2022)
Article
Mathematics
Junzhen Wang, Jinyu Zou, Shumin Zhang
Summary: This article introduces the important measurement of network connectivity and provides a generalized definition of connectivity. It also proves that the generalized 4-connectivity of the hierarchical star network is equal to n - 1.
Article
Computer Science, Hardware & Architecture
Liqiong Xu, Litao Guo
Summary: This paper examines the component connectivity evaluation in interconnection networks, extending the discussion on k-component connectivity for non-complete connected graphs.
Article
Mathematics, Applied
Huifen Ge, Shumin Zhang, Chengfu Ye, Rongxia Hao
Summary: This paper investigates the generalized 4-connectivity and generalized 3-connectivity of the folded Petersen cube network. It also verifies the generalized 4-connectivity of the hypercube and folded Petersen graph. These conclusions lay a foundation for studying the generalized 4-connectivity of Cartesian product graphs.
Article
Mathematics, Applied
Shu-Li Zhao, Rong-Xia Hao, Jie Wu
Summary: This paper focuses on the generalized 4-connectivity of the hierarchical cubic network HCNn and shows that kappa(4)(HCNn) = n for n >= 3. As a corollary, it is also obtained that kappa(3)(HCNn) = n for n >= 3.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Mathematics, Applied
Meijie Ma, Xiang-Jun Li, Guijuan Wang, Yongli Zan
Summary: Fault-tolerance is an important indicator for measuring the stability of the interconnection network. This study fills the gap in the g-extra connectivity of the enhanced hypercube for specific cases, and derives specific results.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Computer Science, Theory & Methods
Qifan Zhang, Shuming Zhou, Eddie Cheng
Summary: Classical connectivity and component connectivity are important metrics to assess fault tolerance and reliability of network-based multiprocessor systems. This paper determines the (r+1)-component connectivity of augmented cubes.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Computer Science, Interdisciplinary Applications
Tianlong Ma, Eddie Cheng, Yaping Mao, Xu Wang
Summary: This paper investigates the maximum fractional matching of a graph and provides some sufficient and necessary conditions to characterize it. Furthermore, it also obtains sharp lower bounds of the fractional matching number for Cartesian product, strong product, lexicographic product, and direct product.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Computer Science, Hardware & Architecture
Yanze Huang, Limei Lin, Eddie Cheng, Li Xu
Summary: This paper focuses on the reliability of a multiprocessor system, with an emphasis on the component diagnosability and component connectivity of a graph. The paper proposes the r-component diagnosability of the n-dimensional alternating group graph AG(n) under the PMC model, and presents a good construction for the general r-component connectivity of AG(n) where 6 <= r <= n - 1. Theoretical analysis and simulation results show that the general r-component connectivity of AG(n) is higher than that of Q(n), D-n, and FQ(n).
Article
Computer Science, Theory & Methods
Eddie Cheng, Laszlo Liptak, Ke Qiu, Zhizhang Shen
Summary: This article discusses the importance of connectivity type measures in network analysis, particularly in analyzing vulnerability and resiliency of interconnection networks. The article studies a way to extend known results in this area by considering the structure of the resulting graph when many vertices are deleted.
JOURNAL OF INTERCONNECTION NETWORKS
(2022)
Article
Mathematics, Applied
Xiao-Chen Li, Rong-Xia Hao
Summary: In this paper, we investigate the vertex Turan density and bounds of forbidden configurations in the k-ary n-cube. We derive exact values and boundaries for different forbidden configurations and dimensions. The findings are significant for understanding and analyzing the structural properties of the n-cube.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Mathematics, Applied
Jinyu Zou, Yaping Mao, Zhao Wang, Eddie Cheng
Summary: This paper investigates the fractional matching preclusion number of a graph, providing sharp upper and lower bounds for this number. It also characterizes graphs with large and small fractional matching preclusion numbers. Furthermore, it explores extremal problems related to the fractional matching preclusion number.
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Computer Science, Theory & Methods
Mohamad Abdallah, Eddie Cheng
Summary: This paper focuses on a class of Cayley graphs generated by certain 3-cycles on the alternating group An as models for interconnection networks. The fault-Hamiltonian connectivity of these graphs is analyzed, and it is proven that these graphs are (2n - 7)-fault-tolerant Hamiltonian connected.
THEORETICAL COMPUTER SCIENCE
(2022)
Article
Computer Science, Theory & Methods
Mohamad Abdallah, Eddie Cheng
Summary: This article investigates the conditional strong matching preclusion number for the pancake graph, which is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings.
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS
(2023)
Article
Mathematics, Applied
Wen -Han Zhu, Rong-Xia Hao, Yan-Quan Feng, Jaeun Lee
Summary: In this paper, we investigate the Omega-paths and path connectivity in a connected simple graph G. By deeply exploring the structural properties of the k-ary n-cube Q(n)(k), we completely determine its 3-path connectivity.
APPLIED MATHEMATICS AND COMPUTATION
(2023)
Article
Computer Science, Theory & Methods
Hui Zhang, Rong-Xia Hao, Xiao-Wen Qin, Cheng-Kuan Lin, Sun-Yuan Hsieh
Summary: This paper investigates the applications of matroidal connectivity and conditional matroidal connectivity in alternating group graphs and proves the connectivity under certain conditions. The experimental results show that the matroidal connectivity significantly improves the fault-tolerant capability of alternating group graphs.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2023)
Article
Computer Science, Theory & Methods
Xiaoqing Liu, Shuming Zhou, Eddie Cheng, Hong Zhang
Summary: With the rapid development of network technology, a multiprocessor system consisting of multiple processors and communication links plays a significant role in the big data era. The topology of a multiprocessor system greatly influences network performance and the design of a high-performance network architecture is of great importance. This paper proposes a more general class of balanced hypercubes and explores their basic properties. It also demonstrates the connectivity, super connectivity, extra connectivity, and (extra) diagnosability of these hypercubes. (c) 2022 Elsevier B.V. All rights reserved.
THEORETICAL COMPUTER SCIENCE
(2023)
Article
Computer Science, Hardware & Architecture
Hong Zhang, Shuming Zhou, Eddie Cheng
Summary: In this work, a novel diagnostic strategy based on cyclic connectivity, namely the cyclic diagnosability, is proposed. The cyclic diagnosability of hypercube Q(n) under the PMC model and the MM* model is investigated, and it is shown that ct(Q(n)) = 5n -10 for n = 7.
Article
Mathematics, Applied
Hong Zhang, Shuming Zhou, Eddie Cheng
Summary: This study investigates the m-restricted (edge) connectivity of the Cayley graph En, generated by G(X) with a maximum matching number h. When 1 < m < h, it is proven that the m-restricted (edge) connectivity of En is Kappa m(En) = 2m(n - 1 - m) (resp., lambda m(En) = 2m(n - 1 - m)).
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Mathematics, Applied
Hui Zhang, Rong-Xia Hao, Hong-Jian Lai, Jaeun Lee
Summary: This paper explores some properties of the n-dimensional bubble-sort star graph BSn and proves that when n ≥ 4, for any even integer l satisfying 4 < l < n!/2, there exist two vertex-disjoint cycles C1 and C2 in BSn such that |C1| = l and |C2| = n! - l. This result supplements the Hamiltonicity and the bipancyclicity of BSn.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Mathematics
Yaping Mao, Christopher Melekian, Eddie Cheng
Summary: In a connected graph G=(V, E), an S-Steiner tree is a subgraph T=(V', E') that is a tree with a vertex subset S of V(G). If each vertex of S in T has a degree of 1, it is called a pendant S-Steiner tree. Two S-Steiner trees are internally disjoint if they do not share any vertices other than S and have no common edges. The pendant tree-connectivity tau(G)(S) is the maximum number of internally disjoint pendant S-Steiner trees in G for S subset of V(G) with |S|>=2, and the k-pendant tree-connectivity tau(k)(G) is the minimum value of tau(G)(S) among all sets S with k vertices. We provide a lower bound for tau(3)(G o H), where G and H are connected graphs and o denotes the lexicographic product.
CZECHOSLOVAK MATHEMATICAL JOURNAL
(2023)
Proceedings Paper
Mathematics, Applied
Eddie Cheng, Laszlo Liptak, Daniel Tian
Summary: This paper explores the concept of Extraconnectivity and computes the g-extraconnectivity of small arrangement graphs (with g <= 6). Additionally, an asymptotic result for general g is provided.
COMBINATORICS, GRAPH THEORY AND COMPUTING, SEICCGTC 2020
(2022)
Article
Mathematics, Applied
Yuehua Bu, Peng Wang, Hongguo Zhu, Junlei Zhu
Summary: This paper investigates the injective-edge coloring of a sparse graph G, and proves that when mad(G) meets certain conditions, the injective chromatic index x(i)'(G) has a upper bound.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Fawad Ali, Bilal A. Rather, Muhammad Naeem, Wei Wang
Summary: A topological descriptor is a numerical value derived from the molecular structure and is related to the important structural characteristics of the molecule. It is used to describe the composition of chemicals and their relationship with physical properties. This article explores various topological indices for power graphs of different finite groups.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Sergio Bermudo, Roslan Hasni, Fateme Movahedi, Juan E. Napoles
Summary: This article introduces a new graph index, the geometric-arithmetic index, and discusses the upper and lower bounds for this index in trees.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Ran Gu, Hui Lei, Yongtang Shi, Yiqiao Wang
Summary: This paper discusses the existence of rainbow-free coloring in random k-uniform hypergraphs, and provides the threshold function and the answer.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Fengwei Li, Qingfang Ye, Huajing Lu
Summary: This paper introduces the definition and application of the atom-bond sum-connectivity index (ABS index), and discusses its importance in studying molecular structures.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Milan Basic
Summary: This passage mainly describes the definition of integral circulant graph ICGn(D), the condition for adjacent vertices, and the characterization of minimal spread in the class of connected integral circulant graphs of a given order.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Andrey A. Dobrynin, Konstantin V. Vorob'ev
Summary: This study investigates the relationship between the Wiener index and R-m(G) of a graph G, and establishes the existence and properties of graphs G that satisfy specific conditions.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Devsi Bantva, Daphne Der-Fen Liu
Summary: This paper provides a lower bound for the radio number of the Cartesian product of two trees and presents three necessary and sufficient conditions as well as three sufficient conditions for achieving this bound. By applying these results, the radio number of the Cartesian product of two stars as well as a path and a star is determined.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Mikhail Fadin
Summary: This article discusses rational lattices, octahedral defects, and their relationship with monotonic increasing functions.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Jian Lu, Huiqing Liu, Xiaolan Hu
Summary: This paper investigates the problem of strong edge-coloring, and proves that when certain conditions are satisfied, the upper bound of the strong chromatic index is 29, thereby verifying Erdos' conjecture under certain circumstances.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Tom Denat, Ararat Harutyunyan, Nikolaos Melissinos, Vangelis Th. Paschos
Summary: This paper studies the average-case complexity of a branch-and-bound algorithm for the MIN DOMINATING SET problem in random graphs. We identify phase transitions between subexponential and exponential average-case complexities, depending on the growth of the probability p with respect to the number n of nodes.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Lkhagva Buyantogtokh, Batmend Horoldagva
Summary: This paper discusses the application of the exponential second Zagreb index in graphs and proves a conjecture regarding the maximum index. It also identifies the properties of graphs with maximum index under certain conditions.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Shenwei Huang, Yiao Ju, T. Karthick
Summary: This paper studies the coloring of (P5, kite)-free graphs with small clique number. It provides color number bounds for different constraints on cliques and proves them for specific conditions. The paper also gives examples to demonstrate the tightness of the bounds and makes a conjecture for the more general case.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Ryul Kim
Summary: This paper establishes relations between irreducible polynomials over a finite field Fq and its quadratic extension Fq2. The paper considers the relation between the numbers of irreducible polynomials of a fixed degree over Fq and Fq2, as well as the relations between self-reciprocal irreducible polynomials over Fq and self-conjugatereciprocal irreducible polynomials over Fq2. The paper also provides formulas for the number and the product of all self-conjugate-reciprocal irreducible monic (SCRIM) polynomials over Fq2.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Beata Benyi, Sithembele Nkonkobe
Summary: This paper introduces and lists weighted alpha-distanced words, showing their connection to the unified Apostol-type polynomials and providing combinatorial proofs of certain identities.
DISCRETE APPLIED MATHEMATICS
(2024)