Article
Computer Science, Hardware & Architecture
Yifeng Wang, Baolei Cheng, Yu Qian, Dajin Wang
Summary: This paper investigates the number of CISTs that can be constructed in the line graph of a complete graph and presents an algorithm for constructing the optimal number of CISTs. The findings have significant implications for assessing network robustness.
IEEE TRANSACTIONS ON COMPUTERS
(2022)
Article
Mathematics, Applied
Xia Hong, Wei Feng
Summary: For a graph G, if there exist k spanning trees T-1, T-2, ..., T-k, such that the paths from any two vertices u, v in these k trees are pairwise openly disjoint, then these k trees are completely independent. Hasunuma proved that there are two completely independent spanning trees in any 4-connected maximal planar graph, and the problem of deciding whether there exist two completely independent spanning trees in a given graph G is NP-complete. This paper investigates the number of completely independent spanning trees in some Cartesian product graphs.
Article
Mathematics, Applied
Xiaodong Chen, Qinghai Liu, Xiwu Yang
Summary: A graph G is a split graph if its vertex set V(G) can be partitioned into a clique D and an independent set I. In this paper, we prove that a Hamiltonian split graph with |D| > max{3, |I|} contains two completely independent spanning trees (CISTs). We also show that a Hamiltonian split graph with a toughness value r(G) > 1 contains two CISTs. As a corollary, we obtain that every 32-tough split graph contains two CISTs.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Mathematics
Xiaodong Chen, Mingchu Li, Liming Xiong
Summary: This paper investigates the existence of two completely independent spanning trees in a graph and its relationship with the closure of the graph.
DISCRETE MATHEMATICS
(2022)
Article
Mathematics
Jun Yuan, Ru Zhang, Aixia Liu
Summary: This paper focuses on the sufficient conditions for bipartite graphs to possess k completely independent spanning trees. It provides two inequalities for the number of elements and degrees, and when these inequalities are satisfied, the bipartite graph has k completely independent spanning trees.
GRAPHS AND COMBINATORICS
(2022)
Article
Computer Science, Hardware & Architecture
Yifeng Wang, Baolei Cheng, Jianxi Fan, Yu Qian, Ruofan Jiang
Summary: In this paper, a general algorithm is proposed for the first time to establish the relationship between edge-disjoint spanning trees in an interconnection network and its line graph, leading to the discovery of more completely independent spanning trees. Furthermore, the lack of results regarding CISTs on line graphs is highlighted.
Article
Mathematics
Richard Lang, Nicolas Sanhueza-Matamala
Summary: We study conditions in dense graphs that guarantee the existence of vertex-spanning substructures such as Hamilton cycles. Our main result generalises this phenomenon to powers of cycles and graphs of sublinear bandwidth subject to natural generalisations of connectivity, matchings and odd cycles. This resolves the embedding problem underlying research on sufficient conditions for spanning structures in dense graphs. As applications, we establish various Bandwidth Theorems in different settings, including Ore-type degree conditions, Posa-type degree conditions, deficiency-type conditions, locally dense and inseparable graphs, multipartite graphs and robust expanders.
PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY
(2023)
Article
Mathematics
Toru Hasunuma
Summary: This paper investigates the maximum number of completely independent spanning trees in a line graph and provides various results and properties.
GRAPHS AND COMBINATORICS
(2023)
Article
Mathematics
Xiaodong Chen, Jingjing Li, Fuliang Lu
Summary: This paper proves that a P4-free graph G contains two completely independent spanning trees if and only if G is a 2-connected graph and belongs to a specific graph family. Moreover, it is also shown that every 1-tough P4-free graph G, belonging to another graph family, contains two completely independent spanning trees.
GRAPHS AND COMBINATORICS
(2023)
Article
Computer Science, Information Systems
Dun-Wei Cheng, Kai-Hsun Yao, Sun-Yuan Hsieh
Summary: The generalized recursive circulant networking can be widely applied in the design and implementation of interconnection networks, with processors connected through bidirectional, point-to-point communication channels. By applying the concept of shortest path routing to build independent spanning trees, this approach loosens previous research restrictions and extends results to a more general vertex setting using a specific algorithm to address constraint issues.
Article
Engineering, Multidisciplinary
Kung-Jui Pai, Jinn-Shyong Yang, Guan-Yu Chen, Jou-Ming Chang
Summary: The existence of multiple completely independent spanning trees (CISTs) in a network has significant applications in fault-tolerant routing and secure message distribution. This paper proposes linear-time algorithms for constructing dual CISTs in dense Gaussian networks (DGNs) and evaluates the performance of protection routing in DGNs using simulation results.
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING
(2022)
Article
Computer Science, Theory & Methods
Guo Chen, Baolei Cheng, Dajin Wang
Summary: This article discusses the importance and applications of constructing Completely Independent Spanning Trees (CISTs) in a network, especially in data center networks. It also introduces the augmented cube AQn as the underlying structure of a data center network and studies how to construct n-1 optimal CISTs in its logic graph L-AQDNn. Additionally, the relationship between the dimension of a hypercube-family network and the number of CISTs it can host is established for the first time.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2021)
Article
Physics, Fluids & Plasmas
C. Tyler Diggans, Erik M. Bollt, Daniel ben-Avraham
Summary: This study presents a link-by-link rule-based method for constructing a collection of spanning trees with desired properties, offering a solution for optimization problems in complex networks.
Article
Computer Science, Theory & Methods
Xiao-Yan Li, Wanling Lin, Ximeng Liu, Cheng-Kuan Lin, Kung-Jui Pai, Jou-Ming Chang
Summary: The paper investigates the construction of completely independent spanning trees (CISTs) in a server-centric data center network called BCube connected crossbars (BCCC) for fault-tolerant routing. The network offers good performance and reliability, with the fault-tolerant routing evaluated through simulation results.
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS
(2022)
Article
Computer Science, Theory & Methods
Baolei Cheng, Dajin Wang, Jianxi Fan
Summary: This survey provides a comprehensive collection of important works on ISTs and offers a historical perspective on the development of ISTs, serving as a useful reference for future research in this field.
ACM COMPUTING SURVEYS
(2023)
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)