Article
Mathematics
Shasha Li
Summary: The paper discusses Steiner trees in graphs and their internal and edge disjoint properties, as well as the concepts of k-tree connectivity and k-tree edge-connectivity. The research confirms a conjecture about connected graphs and highlights the sharpness of the bounds.
DISCRETE MATHEMATICS
(2021)
Article
Mathematics
Hengzhe Li, Huayue Liu, Jianbing Liu, Yaping Mao
Summary: This paper investigates two conjectures about connectivity in graphs and provides proofs for certain special cases of these conjectures.
GRAPHS AND COMBINATORICS
(2023)
Article
Mathematics, Applied
Yuan Chen, Guowei Dai, Zhiquan Hu
Summary: This paper investigates two necessary conditions for Pk-factors in the squares and line graphs of trees. The results are shown to be best possible in some sense. Additionally, a characterization is provided for a class of trees whose line graphs contain P4-factors.
APPLIED MATHEMATICS AND COMPUTATION
(2023)
Article
Mathematics, Applied
Shu-Li Zhao, Rong-Xia Hao, Chao Wei
Summary: This paper investigates the generalized 4-connectivity of the line graph L(K-m,K-n) and total graph T(K-m,K-n), and obtains several results.
APPLIED MATHEMATICS AND COMPUTATION
(2022)
Article
Mathematics
Dandan Fan, Xiaofeng Gu, Huiqiu Lin
Summary: The spanning tree packing number tau(G) of a graph G is the maximum number of edge-disjoint spanning trees contained in G. The study of tau(G) is a classic problem in graph theory. This paper further extends previous results and proves tight sufficient conditions for tau(G)>= k, as well as characterizes extremal graphs. Additionally, the paper confirms a conjecture on characterizing graphs with the maximum spectral radius, and discusses applications in rigidity and nowhere-zero flows. The paper concludes with some open problems.
JOURNAL OF GRAPH THEORY
(2023)
Article
Computer Science, Theory & Methods
Xingfu Li, Guihai Yu, Sandi Klavzar, Jie Hu, Bo Li
Summary: In this study, we investigated the Steiner k-eccentricity on trees, extending the concept from a previous paper. We developed a stronger properties for the Steiner k-ecc tree than what was previously known and devised a linear time algorithm to calculate the Steiner k-eccentricity of a vertex in a tree. Additionally, we established lower and upper bounds for the average Steiner k-eccentricity index of a tree using a novel technique that is easier to follow compared to the earlier one.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Computer Science, Hardware & Architecture
Kaige Pan, Dongqin Cheng
Summary: This paper introduces the definitions of structure connectivity and substructure connectivity, and investigates star structure and star substructure connectivity of Cayley graphs generated by transposition trees.
JOURNAL OF SUPERCOMPUTING
(2023)
Article
Mathematics
Jieyan Wang
Summary: The paper discusses the concepts of embeddings and packings of graphs, and proves that for any tree T of order n, there exists a 4-packing of T in a complete bipartite graph of order at most n + 12.
DISCUSSIONES MATHEMATICAE GRAPH THEORY
(2022)
Article
Mathematics, Applied
Zemin Jin, Xueyao Gui, Kaijun Wang
Summary: The paper discusses the problem of using up to k colors in the edge coloring of graphs, and determines the color number for trees.
APPLIED MATHEMATICS AND COMPUTATION
(2021)
Article
Management
David Whittle, Marcus Brazil, Peter Alexander Grossman, Joachim Hyam Rubinstein, Doreen A. Thomas
Summary: This paper investigates the relationship between the length of a minimum Steiner tree and a minimum spanning tree in a configuration of concyclic points in the Euclidean plane, proving a tight lower bound on their difference. This bound can be used as part of an efficient algorithm for solving the prize-collecting Euclidean Steiner tree problem.
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
(2022)
Article
Computer Science, Theory & Methods
Hans L. Bodlaender, Nick Brettell, Matthew Johnson, Giacomo Paesani, Daniel Paulusma, Erik Jan van Leeuwen
Summary: In this paper, we study the classical problems of (edge) Steiner Tree and Vertex Steiner Tree after restricting the input to some class of graphs characterized by a small set of forbidden induced subgraphs. We demonstrate a dichotomy for the former problem and the latter problem under different restrictions, and discover specific infinite families of graphs that have polynomial-time solvable solutions for the Vertex Steiner Tree problem.
THEORETICAL COMPUTER SCIENCE
(2021)
Article
Mathematics, Applied
Jiang Zhou, Changjiang Bu, Hong-Jian Lai
Summary: This paper provides bounds on the spanning tree packing number and the arboricity of graphs in terms of effective resistances, offering a calculation method. Applications demonstrate that equiarboreal graphs are uniformly dense and determine the maximum number of edge-disjoint spanning c-forests of equiarboreal graphs. Furthermore, the arboricity of a regular graph can be directly derived from the effective resistance bounds provided.
DISCRETE APPLIED MATHEMATICS
(2021)
Article
Computer Science, Theory & Methods
Tahsin Reza, Trevor Steil, Geoffrey Sanders, Roger Pearce
Summary: In this paper, a parallel 2-approximation Steiner minimal tree algorithm and its distributed implementation using MPI are presented. Instead of expensive distance computations, a cheaper Voronoi cell computation is employed to find the solution. The design of the algorithm utilizes asynchronous processing, message prioritization, and centrality processing to achieve fast convergence and time-to-solution. Experimental results demonstrate scalability, performance, and comparison with other algorithms, showing promising results.
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
(2023)
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
Computer Science, Interdisciplinary Applications
Jianping Li, Junran Lichen, Wencheng Wang, Jean Yeh, YeongNan Yeh, Xingxing Yu, Yujie Zheng
Summary: This paper discusses the 1-line minimum rectilinear Steiner tree problem and provides three main contributions: designing an algorithm to solve the 1-line-fixed-constrained minimum rectilinear Steiner tree problem, proving this algorithm is a 1.5-approximation algorithm to solve the 1-line-fixed minimum rectilinear Steiner tree problem, and presenting a 1.5-approximation algorithm to solve the 1-line minimum rectilinear Steiner tree problem through combining the algorithm for many times and a key lemma proved by techniques of computational geometry.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Mathematics, Applied
Wei Yang, Baoyindureng Wu
Summary: This note disproves three conjectures on power domination of regular graphs, one by Dorbec et al. (2013) and two by Lu et al. (2020).
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Mathematics
Huijuan Yu, Baoyindureng Wu
Summary: This paper establishes sharp upper bound for the P-admission number in a connected graph G and proves that for a connected graph G not equal to C-7 of order n, eta(G, R-1) <= n/4. The bound is sharp. Several related problems are proposed.
GRAPHS AND COMBINATORICS
(2022)
Article
Mathematics, Applied
Tao Wang, Baoyindureng Wu
Summary: In this paper, sharp upper and lower bounds for the size of connected graphs with fixed order and feedback number are established, and corresponding extremal graphs are characterized. As a corollary, a sharp lower bound for the forest number of a graph in terms of its order and size is given, extending a result of Shi and Xu (2017).
DISCRETE APPLIED MATHEMATICS
(2022)
Article
Mathematics
Tao Wang, Baoyindureng Wu
Summary: This paper investigates the forest number of various products of two graphs and provides sharp bounds for some of them. Furthermore, it presents formulas for calculating the forest number in specific cases.
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY
(2023)
Article
Mathematics, Applied
Wei Yang, Baoyindureng Wu
Summary: This article discusses the arc number, color number, and rainbow triangles in a digraph. The researchers proved a conjecture and disproved another one by constructing counterexamples.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Mathematics, Applied
Tao Wang, Baoyindureng Wu, Taishan Wang
Summary: This study discusses the problem of harmonic index of graphs, proves the validity of a conjecture, and proposes new conjectures.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Mathematics, Applied
Tao Wang, Baoyindureng Wu
Summary: A vertex partition (V-1, ... , V-s) of a graph G is called a k-good partition if d(G[Vi]) (v) equivalent to 1 (mod k) for each v is an element of V-i, i is an element of {1, ... , s}. We characterize all trees with a k-good partition. Let f(1,k)(G) = max{vertical bar V (H)vertical bar : H is an induced subgraph Hof G with d(H) (v) equivalent to 1 (mod k) for every vertex v}. In 1997, Berman et al. (1997) showed that f(1,k)(T) >= 2[n+2k-3/2k-1] for any tree T of order n. By sacrificing the bound slightly, but with a much simpler way, we are able to show that f(1,k) (T) >= n/k, with equality if and only if T is the balanced double star of order 2k. Let f(0,k)(1)(T) be the maximum cardinality of a subset S subset of V (T) with d(T[S]) (v) = 1 or d(T[S]) (v) equivalent to 0 (mod k) for each v is an element of S. In addition, we give a short proof of the result, due to Huang and Hou [9], that f(0,k)(1) (T) >= 2n/3 for any tree T and integer k >= 3. (c) 2022 Elsevier Inc. All rights reserved.
APPLIED MATHEMATICS AND COMPUTATION
(2023)
Article
Mathematics
Zhenzhen Li, Baoyindureng Wu
Summary: A path in an edge-colored graph G is conflict-free if only one edge on the path is colored. An edge-colored graph G is conflict-free connected if any two vertices are connected by a conflict-free path. The conflict-free connection number, denoted as cfc(G), of a connected graph G is the minimum number of colors required to make it conflict-free connected.
GRAPHS AND COMBINATORICS
(2023)
Article
Mathematics, Applied
Jiawei Meng, Baoyindureng Wu, Hongliang Ma
Summary: This paper provides an explicit characterization for all graphs G with L-2(G) being a complete graph. Lower bounds for the clique number and chromatic number of L-2(G) are presented for several classes of graphs. In addition, bounds for the domination number of L-2(G) are established in terms of the domination number of the line graph L(G) of a graph. Several related problems on L-2(G) are proposed for further study.
Article
Mathematics, Applied
Tongtong Xu, Baoyindureng Wu
Summary: For two graphs H and F, a spanning subgraph G of H is weakly (H, F) -saturated if there is no subgraph isomorphic to F in G, but there is an ordering of the elements in E(H) \ E(G) so that they can be added one at a time, and each addition of an element yields a subgraph F⠃ isomorphic to F. The weak saturation number wsat(H, F) of F with respect to H is the minimum size of a weakly (H, F)-saturated graph. Upper bounds for wsat(Kn, rKa, a) and wsat(Kn, rKa, a+1) are given for any two integers r ≥ 3 and a ≥ 1, respectively. An upper bound of wsat(Kn, Ka, b) is established for integers n, a, b satisfying a + 1 < b < 3a - 2, a ≥ 3 and n ≥ 2(a + b - 2). This provides a negative answer to a question raised by Kronenberg et al. regarding wsat(Kn, Ka, a+2) in the clique.
APPLIED MATHEMATICS AND COMPUTATION
(2023)
Article
Mathematics, Applied
Wei Yang, Baoyindureng Wu
Summary: A packing S-coloring of a graph G is a partition of V(G) into subsets such that the distance between any two distinct vertices in a subset is at least the corresponding element in the sequence S. Gastineau and Togni asked if every 3-irregular subcubic graph packing (1, 1, 3)-colorable, and we improve upon their result by showing that it is true. Kostochka and Liu proposed the question of whether every subcubic 2-connected outerplanar graph packing (1, 2, 2, 2)-colorable, and we prove that it is indeed true.
DISCRETE APPLIED MATHEMATICS
(2023)
Article
Mathematics
Wei Yang, Baoyindureng Wu
Summary: The k-component domination number ?(k)(G) of G is the minimum cardinality of a dominating set S of G such that each connected component of G[S] has order at least k. It is known that ?(1)(G) is the domination number of G and ?(2)(G) is the total domination number of G. In this paper, it is proven that if G is a connected graph of order n = k + 1 = 4, then ?(k)(G) = (k+2)/(km+1), and this bound is sharp.
GRAPHS AND COMBINATORICS
(2023)
Article
Mathematics
Wei Yang, Baoyindureng Wu
Summary: The authors investigated the properties of outer connected dominating sets and their applications in maximal outerplanar graphs and maximal minor-free graphs. They proved a theorem about two types of graphs and disproved a conjecture. Furthermore, they extended the scope of the theorem.
DISCUSSIONES MATHEMATICAE GRAPH THEORY
(2022)
Article
Mathematics, Applied
Jiangfu Zhang, Baoyindureng Wu
Summary: This note discusses the Randic index of a graph and proves a lower bound for the Randic index of a tree. Several relevant conjectures are also proposed.
Article
Mathematics
Fengxia Liu, Baoyindureng Wu, Jixiang Meng
Summary: This paper discusses the properties of arbitrarily partitionable graphs and some special graphs, and gives the necessary and sufficient conditions for arbitrarily partitioning threshold graphs and {2K(2), C-4}-free graphs.
DISCUSSIONES MATHEMATICAE GRAPH THEORY
(2022)
Article
Mathematics
Weijun Fang, Jiejing Wen, Fang-Wei Fu
Summary: This paper proposes a sufficient condition to ensure that a Hermitian self-orthogonal GRS code is still a Hermitian self-orthogonal code. Based on this, a new general construction of infinitely families of quantum MDS codes is presented, and two new constructions of quantum MDS codes with flexible parameters are given using the trace function and norm function over finite fields. The constructed quantum MDS codes have different lengths from previous known results, and the minimum distances of all the q-ary quantum MDS codes are larger than q/2 + 1.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Hoa T. Bui, Guillermo Pineda-Villavicencio, Julien Ugon
Summary: The paper examines the linkedness of the graphs of cubical polytopes and proves that every cubical d-polytope has [d/2] and strong [d/2] linkedness, for every d = 3. These results are optimal for this class of polytopes.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Julia Carrigan, Isaiah Hollars, Eric Rowland
Summary: Two words p and q are avoided by the same number of length-n words, for all n, precisely when p and q have the same set of border lengths. Previous proofs of this theorem use generating functions but do not provide an explicit bijection. We give a bijective proof for all pairs p, q that have the same set of proper borders, establishing a natural bijection from the set of words avoiding p to the set of words avoiding q.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Luke Nelson, Kevin Treat
Summary: We define a poset called the Outer Tamari poset, which is shown to be isomorphic to a subposet of the Tamari lattice introduced by Pallo (1986) and further studied as the Comb poset by Csar, Sengupta, and Suksompong (2014). By using the Outer Tamari poset, we develop recursive formulas for the number of triangulations of the 3-dimensional cyclic polytopes. These triangulations can be considered as elements of both the higher Stasheff-Tamari orders in dimension three and the Tamari Block lattices defined in a previous article. Therefore, our work here can be seen as constructing recursive enumerations of these posets.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Nicholas A. Loehr, Gregory S. Warrington
Summary: This study explores variants of chromatic symmetric functions for rooted graphs and investigates the combinatorial identities and recursions satisfied by these rooted chromatic polynomials. It proves the irreducibility of Stanley's polynomial under certain conditions, establishes conditions for isomorphism of rooted trees as rooted graphs, and provides a combinatorial interpretation of the monomial expansion of pointed chromatic functions.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Shira Zerbib
Summary: This article studies the property of a family of sets and proves that when a family of compact convex sets has a specific intersection property, it can be pierced by a certain number of lines. The proofs are based on the topological KKM theorem.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
David Sossa, Vilmar Trevisan
Summary: The study focuses on the complementarity spectrum and separability index of graphs, demonstrating the relationship between the largest complementarity eigenvalues of graphs of a specific order and deducing the growth trend of the separability index of the set of connected graphs.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Anita Keszler, Zsolt Tuza
Summary: This study considers edge decompositions of K-v((3)) - I and provides decomposition results satisfying certain conditions, complementing previous research findings.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Ping Li
Summary: This paper explores the relationship between monochromatic connection coloring and the connectivity of a graph, providing a method and upper bounds for computing the monochromatic connection number. Additionally, the paper discusses the characteristics of MC-colorings for graphs with specific connectivity requirements.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Santiago Guzman-Pro
Summary: This article discusses the concepts of full-homomorphism, full H-colouring, and minimal H-obstruction. It proves the existence of a finite number of minimal H obstructions for every graph H. Furthermore, it describes the properties of minimal obstructions and poses some related questions.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Rongzhong Xiao
Summary: We prove that for any finite coloring of Q, there exist non-zero elements that satisfy certain conditions.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Robert Lukot'ka
Summary: The article studies the circular flow problem, gives the circular flow number of Goldberg snark G2k+1, and proves a conjecture.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Benjamin Egan, Yuri Nikolayevsky
Summary: A simple graph is called triangular if every edge of it belongs to a triangle. We conjecture that any graphical degree sequence all terms of which are greater than or equal to 4 has a triangular realisation, and establish this conjecture for a class of biregular graphical degree sequences.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Jakub Przybylo
Summary: We improve upon Molloy's breakthrough result by adapting Bernshteyn's proof, achieving a stronger result that states triangle-free graphs can be colored from lists of size (1 +o(1))A/ log A, where vertices sharing a common color do not induce a triangle in G. We also extend this result to graphs of maximum degree A by proving the sufficiency of list sizes (1000 + o(1))A/ log A, as implied by a more general result due to Amini and Reed. Furthermore, we demonstrate that lists of length 2(r - 2)A log2 log2 A/ log2 A are sufficient if one replaces the triangle with any Kr with r >= 4. All of these bounds hold in the context of correspondence colorings.
DISCRETE MATHEMATICS
(2024)
Article
Mathematics
Hongwei Zhu, Minjia Shi
Summary: This paper studies the b-symbol weight hierarchy of Kasami codes and discusses their applications in high density data storage systems.
DISCRETE MATHEMATICS
(2024)