Search

Let G be a connected graph and let k ≥ 1 be an integer. Let T be a spanning tree of G. The leaf degree of a vertex v ∈ V (T) is defined as the number of leaves adjacent to v in T. The leaf degree of T is the maximum leaf degree among all the vertices of T. Let |E(G)| and ρ (G) denote the size and the spectral radius of G, respectively. In this paper, we first create a lower bound on the size of G to ensure that G admits a spanning tree with leaf degree at most k. Then we establish a lower bound on the spectral radius of G to guarantee that G contains a spanning tree with leaf degree at most k. Finally, we create some extremal graphs to show all the bounds obtained in this paper are sharp. [ABSTRACT FROM AUTHOR]

We give a short proof of the fact that the number of labeled trees on n vertices is n n − 2 . Although many short proofs are known, we have not seen this one before. [ABSTRACT FROM AUTHOR]

A graph in which all minimal zero forcing sets are in fact minimum zero forcing sets is called a well-forced graph. The main result of this paper is to characterize well-forced trees and based on this characterization present an algorithm for determining which trees are well-forced. As part of this characterization, certain subgraphs are identified as being forbidden in a well-forced graph. Additionally it is shown whether some common families of graphs are well-forced or not. Understanding well-forced graphs turns out to be closely related to the question of which vertices of a graph are in a minimal zero forcing set. A vertex of G that is in no minimal zero forcing set of G is called an irrelevant vertex. For any graph, a sufficient condition for a vertex to be irrelevant is established. In addition, it is proved that this condition is a characterization of irrelevant vertices in trees. [ABSTRACT FROM AUTHOR]

Let H = (V , E) be a hypergraph. A subset S ⊆ V is called F -isolating of H if the induced subhypergraph H [ V \ N [ S ] ] contains no any member in F as a subhypergraph. The F -isolation number of H is the minimum cardinality of an F -isolating set of H, denoted by ι (H , F) . A subset S ⊆ V is an isolating set of H if V \ N [ S ] is an independent set of H. The cardinality of a minimum isolating set of H is called the isolation number of H, denoted by ι (H) . In this paper, we introduce the F -isolating set of hypergraphs and give some results about the F -isolation number of hypergraphs. [ABSTRACT FROM AUTHOR]

Let G be a simple connected undirected graph. The Laplacian spectral ratio of G is defined as the quotient between the largest and second smallest Laplacian eigenvalues of G, which is an important parameter in graph theory and networks. We obtain some bounds of the Laplacian spectral ratio in terms of the number of the spanning trees and the sum of powers of the Laplacian eigenvalues. In addition, we study the extremal Laplacian spectral ratio among trees with n vertices, which improves some known results of Z. You and B. Liu (2012). [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices, and d i be the degree of its i-th vertex. The ABS matrix of G is the square matrix of order n whose (i, j)-entry is equal to (d i + d j - 2) / (d i + d j) if the i-th vertex and the j-th vertex of G are adjacent, and 0 otherwise. Let ρ 1 ≥ ρ 2 ≥ ⋯ ≥ ρ n be the eigenvalues of the ABS matrix of G. Then the ABS Estrada index of G, denoted by E ABS (G) , is defined as E ABS (G) = ∑ i = 1 n e ρ i . In this paper, the chemical importance of the ABS Estrada index is investigated and it is shown that the predictive ability of ABS Estrada index is stronger than other connectivity Estrada indices (including Randić Estrada index, harmonic Estrada index and ABC Estrada index) and ABS index for octane isomers. Since chemical graphs of octane isomers are trees, we study the extremal problem of ABS Estrada index of trees, and prove that for any tree T n with n ≥ 3 vertices, E ABS (P n) ≤ E ABS (T n) ≤ E ABS (K 1 , n - 1) with equality in the left (resp., right) inequality if and only if T n is isomorphic to the path P n (resp., the star K 1 , n - 1 ). [ABSTRACT FROM AUTHOR]

We provide a characterization of Carleson measures on locally finite trees. This characterization establishes the connection between Carleson measures and the boundedness of a suitable Poisson integral between L p -spaces. Additionally, when the tree has bounded degree, we investigate the relationship between Carleson measures and BMO functions defined on the boundary of the tree. [ABSTRACT FROM AUTHOR]

For an oriented tree, we compute several graph invariants, including the minimal norm of the generalized inverse and the norm of the Moore–Penrose inverse of its incidence matrix. We present equivalent characterizations of these invariants in terms of the minimal ratios of vector norms related to the oriented tree's incidence matrix. We also provide a method to find the optimal vertex cut and edge cut with respect to these invariants. [ABSTRACT FROM AUTHOR]

A set is called a general position set of a graph G if any triple set V0 of R is non-geodesic, that is, three elements of V0 cannot lie on the same geodesic of G. The general position number gp(G) of a graph G is the cardinality of a largest general position set of G. The k-th power, Gk, of a graph G is obtained from G by adding a new edge between each pair of vertices with a distance of at most k in G. In this paper we establish the bounds for gp(Gk) and and give an explicit formula of. Also we consider the relation between gp(G2) and gp(G). We deduce a formula of and provide the upper bound on gp(G2)−gp(G) for general block graphs G. Moreover, we determine the gp-number for the square of trees. [ABSTRACT FROM AUTHOR]

It is known that the following five counting problems lead to the same integer sequence f t (n) : the number of nonequivalent compact Huffman codes of length n over an alphabet of t letters, the number of "nonequivalent" complete rooted t-ary trees (level-greedy trees) with n leaves, the number of "proper" words (in the sense of Even and Lempel), the number of bounded degree sequences (in the sense of Komlós, Moser, and Nemetz), and the number of ways of writing 1 = 1 t x 1 + ⋯ + 1 t x n with integers 0 ≤ x 1 ≤ x 2 ≤ ⋯ ≤ x n . In this work, we show that one can compute this sequence for all n < N with essentially one power series division. In total we need at most N 1 + ε additions and multiplications of integers of cN bits (for a positive constant c < 1 depending on t only) or N 2 + ε bit operations, respectively, for any ε > 0 . This improves an earlier bound by Even and Lempel who needed O (N 3) operations in the integer ring or O (N 4) bit operations, respectively. [ABSTRACT FROM AUTHOR]

Let k ≥ 2 be an integer. A tree T is called a k-tree if d T (v) ≤ k for each v ∈ V (T) ; that is, the maximum degree of a k-tree is at most k. A k-tree T is a spanning k-tree if T is a spanning subgraph of a connected graph G. Let λ 1 (D (G)) denote the distance spectral radius in G, where D(G) denotes the distance matrix of G. In this paper, we verify an upper bound for λ 1 (D (G)) in a connected graph G to guarantee the existence of a spanning k-tree in G. [ABSTRACT FROM AUTHOR]

AbstractThe eccentricity index of a graph is the sum of the eccentricities of all vertices in the graph. A segment S of a tree T is a subgraph isomorphic to a non-trivial path where all internal vertices have degree 2 in T and the end-vertices are branching vertices or leaves. The segment sequence of a tree is the sequence of the lengths of all segments in a tree. In this paper, we characterise trees of a given segment sequence with minimum eccentricity index. We show that in the family of trees of a given segment sequence, the tree with minimum eccentricity index is the unique ‘starlike’ tree (a tree with one branching vertex). [ABSTRACT FROM AUTHOR]

For a graph G, let R (C (n G)) denote the least N such that every 2-colouring of the edges of K N contains a monochromatic copy of nG in a monochromatic connected subgraph, where nG denotes n vertex disjoint copies of G. Gyárfás and Sárközy (J Graph Theory 83(2):109–119, 2016) showed that R (C (n K 3)) = 7 n - 2 for n ≥ 2 . After that, Roberts (Electron J Comb 24(1):8, 2017)showed that R (C (n K r)) = (r 2 - r + 1) n - r + 1 for r ≥ 4 and n ≥ R (K r) , where R (K r) is the Ramsey number of K r . In this paper, we determine R (C (n G)) for all 4-vertex graphs G without isolated vertices. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph. For an edge e = x y ∈ E , the closed neighbourhood of e, denoted by N G [ e ] or N G [ x y ] , is the set N G [ x ] ∪ N G [ y ] . A vertex set L ⊆ V is liar’s vertex-edge dominating set of a graph G = (V , E) if for every e i ∈ E , | N G [ e i ] ∩ L | ≥ 2 and for every pair of distinct edges e i and e j , | (N G [ e i ] ∪ N G [ e j ]) ∩ L | ≥ 3 . This paper introduces the notion of liar’s vertex-edge domination which arises naturally from some applications in communication networks. Given a graph G, the Minimum Liar’s Vertex-Edge Domination Problem (MinLVEDP) asks to find a liar’s vertex-edge dominating set of G of minimum cardinality. In this paper, we study this problem from an algorithmic point of view. We show that MinLVEDP can be solved in linear time for trees, whereas the decision version of this problem is NP-complete for general graphs, chordal graphs, and bipartite graphs. We further study approximation algorithms for this problem. We propose two approximation algorithms for MinLVEDP in general graphs and p-claw free graphs. On the negative side, we show that the MinLVEDP cannot be approximated within 1 2 (1 8 - ϵ) ln | V | for any ϵ > 0 , unless N P ⊆ D T I M E (| V | O (log (log | V |)) . Finally, we prove that the MinLVEDP is APX-complete for bounded degree graphs and p-claw-free graphs for p ≥ 6 . [ABSTRACT FROM AUTHOR]

We study the mapping properties of the Hardy–Littlewood fractional maximal operator between Lorentz spaces of the homogeneous tree and discuss the optimality of all the results. [ABSTRACT FROM AUTHOR]

A travel groupoid is an algebraic system satisfying two suitable conditions, which has a relation to graphs. In this article, we characterize travel groupoids on finite complete multipartite graphs, and we give the numbers of travel groupoids on the complete multipartite graphs. [ABSTRACT FROM AUTHOR]

A signed total double Roman dominating function (STDRDF) on an isolated-free graph [Formula: see text] is a function [Formula: see text] such that (i) every vertex v with [Formula: see text] has at least two neighbors assigned 2 under f or one neighbor w with f(w) = 3, (ii) every vertex v with f(v) = 1 has at least one neighbor w with [Formula: see text] and (iii) [Formula: see text] holds for any vertex v. The weight of a STDRDF is the value [Formula: see text] The signed total double Roman domination number [Formula: see text] is the minimum weight of a STDRDF on G. In this article, we provide various bounds on [Formula: see text] and we show that the corresponding decision problem is NP-complete for bipartite and chordal graphs. In addition, we determine the signed total double Roman domination number of some classes of graphs including cycles, complete graphs and complete bipartite graphs.

Formulas for the determinant of distance matrix DT{D}_{T} of tree TT are known in the unweighted case and in the case when the edges of TT have commuting variable weights. Associated with the four-point condition (4PC) and a tree TT are two matrices, the Max4PCT{{\rm{Max4PC}}}_{T} and the Min4PCT{{\rm{Min4PC}}}_{T}. These are not full rank matrices and their rank, a basis BB, and formulas for the determinant when restricted to the rows and columns of BB are known. In this work, we generalize both these matrices to the case when the edges of TT have commuting variable weights and determine edge-weighted counterparts of known results.

A linear forest is a graph consisting of paths. In this paper, the authors determine the maximum number of edges in an (m, n)-bipartite graph which does not contain a linear forest consisting of paths on at least four vertices for n ≥ m when m is sufficiently large. [ABSTRACT FROM AUTHOR]

In this paper we introduce and study a new graph-theoretic invariant called the bi-Wiener index. The bi-Wiener index W b (G) of a bipartite graph G is defined as the sum of all (shortest-path) distances between two vertices from different parts of the bipartition of the vertex set of G. We start with providing a motivation connected with the potential uses of the new invariant in the QSAR/QSPR studies. Then we study its behavior for trees. We prove that, among all trees of order n ≥ 4 , the minimum value of W b is attained for the star S n , and the maximum W b is attained at path P n for even n, or at path P n and B n (2) for odd n where B n (2) is a broom with maximum degree 3. We also determine the extremal values of the ratio W b (T n) / W (T n) over all trees of order n. At the end, we indicate some open problems and discuss some possible directions of further research. [ABSTRACT FROM AUTHOR]

The protection number of a vertex $v$ in a tree is the length of the shortest path from $v$ to any leaf contained in the maximal subtree where $v$ is the root. In this paper, we determine the distribution of the maximum protection number of a vertex in simply generated trees, thereby refining a recent result of Devroye, Goh, and Zhao. Two different cases can be observed: if the given family of trees allows vertices of outdegree $1$ , then the maximum protection number is on average logarithmic in the tree size, with a discrete double-exponential limiting distribution. If no such vertices are allowed, the maximum protection number is doubly logarithmic in the tree size and concentrated on at most two values. These results are obtained by studying the singular behaviour of the generating functions of trees with bounded protection number. While a general distributional result by Prodinger and Wagner can be used in the first case, we prove a variant of that result in the second case. [ABSTRACT FROM AUTHOR]

For a subgraph G of a complete graph K n , the K n -complement of G, denoted by K n - G , is the graph obtained from K n - G by removing all the edges of G. In this paper, we express the number of spanning trees of the K n -complement K n - G of a bipartite graph G in terms of the determinant of the biadjcency matrices of all induced balanced bipartite subgraphs of G, which are nonsingular, and we derive formulas of the number of spanning trees of K n - G for various important classes of bipartite graphs G, some of which generalize some previous results. [ABSTRACT FROM AUTHOR]

The total eccentricity index of a connected graph is defined as sum of the eccentricities of all its vertices. In this paper, we give the sharp upper bound on the total eccentricity index over graphs with fixed number of pendant vertices and the sharp lower bound on the same over graphs with fixed number of cut vertices. We also provide the sharp upper bounds on the total eccentricity index over graphs with s cut vertices for s = 0 , 1 , n - 3 , n - 2 and propose a conjecture for 2 ≤ s ≤ n - 4 . [ABSTRACT FROM AUTHOR]

Graph burning is a discrete time process which can be used to model the spread of social contagion. One is initially given a graph of unburned vertices. At each round (time step), one vertex is burned; unburned vertices with at least one burned neighbour from the previous round also becomes burned. The burning number of a graph is the fewest number of rounds required to burn the graph. It has been conjectured that for a graph on n vertices, the burning number is at most ⌈ n ⌉ . We show that the graph burning conjecture is true for trees without degree-2 vertices. [ABSTRACT FROM AUTHOR]

Complementarity spectrum of a connected graph G, denoted by $ \Pi (G) $ Π (G) , is the set of spectral radii of all connected induced subgraphs of G. Further, G is said to be spectrally non-redundant if $ c(G) $ c (G) , the cardinality of $ \Pi (G) $ Π (G) , is equal to $ b(G) $ b (G) , the number of all non-isomorphic induced subgraphs of G. In this paper, we give a sufficient condition for a family of graphs to be spectrally non-redundant. Using this criterion, we show that several infinite families of graphs are spectrally non-redundant. Moreover, we apply the same condition to distinguish graphs by their spectral radius, which illustrates the main reason for associating a graph with its complementarity spectrum. [ABSTRACT FROM AUTHOR]

We use the language of proper CAT(-1) spaces to study thick, locally compact trees, the real, complex and quaternionic hyperbolic spaces and the hyperbolic plane over the octonions. These are rank 1 Euclidean buildings, respectively rank 1 symmetric spaces of non-compact type. We give a uniform proof that these spaces may be reconstructed using the cross ratio on their visual boundary, bringing together the work of Tits and Bourdon. [ABSTRACT FROM AUTHOR]

Phylogenetic diversity indices provide a formal way to apportion evolutionary history amongst living species. Understanding the properties of these measures is key to determining their applicability in conservation biology settings. In this work, we investigate some questions posed in a recent paper by Fischer et al. (Syst Biol 72(3):606–615, 2023). In that paper, it is shown that under certain extinction scenarios, the ranking of the surviving species by their Fair Proportion index scores may be the complete reverse of their ranking beforehand. Our main results here show that this behaviour extends to a large class of phylogenetic diversity indices, including the Equal-Splits index. We also provide a necessary condition for reversals of Fair Proportion rankings to occur on phylogenetic trees whose edge lengths obey the ultrametric constraint. Specific examples of rooted phylogenetic trees displaying these behaviours are given and the impact of our results on the use of phylogenetic diversity indices more generally is discussed. [ABSTRACT FROM AUTHOR]

The Turán number of a graph F is the maximum number of edges in any graph on n vertices containing no F as a subgraph. Let P ℓ denote the path on ℓ vertices. A linear forest, denoted by ∪ i = 1 k P ℓ i , is a forest whose connected components are paths. Lidický et al. (Electron J Combin 20(2):62, 2013) considered the Turán number of linear forests for sufficiently large n. Yuan and Zhang (J Graph Theory 98(3):499–524, 2021) determined the Turán numbers of the linear forests containing at most one odd path for all n and proposed a conjecture, which is confirmed to be true for P 3 ∪ P 2 ℓ + 1 , 2 P 5 , 3 P 5 , 2 P 7 , 2 P 9 , 3 P 7 and 2 P 3 ∪ P 2 ℓ + 1 . Motivated by these results, we determine the Turán numbers of P 9 ∪ P 7 for all n ≥ 16 and characterize all extremal graphs, which partially confirms the conjecture proposed by Yuan and Zhang. [ABSTRACT FROM AUTHOR]

In this paper we investigate some properties of the harmonic Bergman spaces A p (σ) on a q-homogeneous tree, where q ≥ 2 , 1 ≤ p < ∞ , and σ is a finite measure on the tree with radial decreasing density, hence nondoubling. These spaces were introduced by J. Cohen, F. Colonna, M. Picardello and D. Singman. When p = 2 they are reproducing kernel Hilbert spaces and we compute explicitely their reproducing kernel. We then study the boundedness properties of the Bergman projector on L p (σ) for 1 < p < ∞ and their weak type (1,1) boundedness for radially exponentially decreasing measures on the tree. The weak type (1,1) boundedness is a consequence of the fact that the Bergman kernel satisfies an appropriate integral Hörmander's condition. [ABSTRACT FROM AUTHOR]

The k-set tree connectivity, as a natural extension of classical connectivity, is an extremely significant index to measure the fault-tolerance of interconnection networks. For a connected graph G = (V , E) and a subset S ⊆ V , an S-tree T = (V ′ , E ′) of graph G is a tree that contains the subset S. Any two S-trees T and T ′ are internally disjoint if and only if E (T) ∩ E (T ′) = ∅ and V (T) ∩ V (T ′) = S . The cardinality of maximum internally disjoint S-trees is defined as κ G (S) , and the k-set tree connectivity is denoted by κ k (G) = min { κ G (S) | S ⊆ V (G) and | S | = k } . In this note, we determine the 4-set tree connectivity of H F Q n . That is, κ 4 (H F Q n) = n + 1 for n ≥ 7 , where H F Q n is hierarchical folded hypercube. [ABSTRACT FROM AUTHOR]

In this paper we initiate the study of the forward and backward shifts on the discrete generalized Hardy space of a tree and the discrete generalized little Hardy space of a tree. In particular, we investigate when these shifts are bounded, find the norm of the shifts if they are bounded, characterize the trees in which they are an isometry, compute the spectrum in some concrete examples, and completely determine when they are hypercyclic. [ABSTRACT FROM AUTHOR]

The transmission of a vertex in a connected graph is the sum of its distances to all the other vertices. A graph is transmission irregular, or TI for short, when all of its vertices have mutually distinct transmissions. In an earlier paper, Al-Yakoob and Stevanović (Appl. Math. Comput. 380:125257, 2020) gave the full characterization of TI starlike trees with three branches. Here, we improve these results by using a different approach to provide the complete characterization of all TI starlike trees. Moreover, we find the precise conditions under which a double starlike tree is TI. Finally, we implement the aforementioned conditions in order to find several infinite families of TI starlike trees and TI double starlike trees. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix $ A(G) $ A (G). Let $ \tau (G) $ τ (G) denote the smallest positive eigenvalue of $ A(G) $ A (G). In 1990, Pavlíková and Kr $ \breve{c} $ c ˘ -Jediný proved that among all nonsingular trees on n = 2m vertices, the comb graph (obtained by taking a path on m vertices and adding a new pendant vertex to every vertex of the path) has the maximum τ value. We consider the problem for unicyclic graphs. Let $ \mathscr {U} $ U denote the class of all connected bipartite unicyclic graphs with a unique perfect matching, and for each $ m\geq ~3 $ m ≥ 3 , let $ \mathscr {U}_n $ U n be the subclass of $ \mathscr {U} $ U with graphs on n = 2m vertices. We first obtain the classes of unicyclic graphs U in $ \mathscr {U} $ U such that $ \tau (U)\leq \sqrt {2}-1 $ τ (U) ≤ 2 − 1. We then find the unique graph $ U_o^n $ U o n (resp. $ U_e^n $ U e n ) having the maximum τ value among all graphs in $ \mathscr {U}_n $ U n when m is odd (resp. when m is even). Finally, we prove that $ U_o^6 $ U o 6 (the graph obtained from a cycle of order 4, by adding two pendants to two adjacent vertices) is the graph with maximum τ value among all graphs in $ \mathscr {U} $ U . As a consequence, we obtain a sharp upper bound for $ \tau (U) $ τ (U) when $ U\in \mathscr {U} $ U ∈ U . [ABSTRACT FROM AUTHOR]

A nonnegative integer p is realizable by a graph-theoretical invariant I if there exists a graph G such that I (G) = p . The inverse problem for I consists of finding all nonnegative integers p realizable by I. In this paper, we consider and solve the inverse problem for the Mostar index, a recently introduced graph-theoretical invariant which attracted a lot of attention in recent years in both the mathematical and the chemical community. We show that a nonnegative integer is realizable by the Mostar index if and only if it is not equal to one. Besides presenting the complete solution to the problem, we also present some empirical observations and outline several open problems and possible directions for further research. [ABSTRACT FROM AUTHOR]

We study ideal-simple commutative semirings and summarize the results giving their classification, in particular when they are finitely generated. In the principal case of (para)semifields, we then consider their minimal number of generators and show that it grows linearly with the depth of an associated rooted forest. [ABSTRACT FROM AUTHOR]

We give a new elementary proof of El Sahili conjecture El Sahili (Discrete Math 287:151–153, 2004) stating that any n-chromatic digraph D, with n ≥ 4 , contains a path with two blocks of order n. [ABSTRACT FROM AUTHOR]