Journal articles: 'Trees (graph theory)'

1

McKee, Terry A. "Subgraph trees in graph theory." Discrete Mathematics 270, no. 1-3 (August 2003): 3–12. http://dx.doi.org/10.1016/s0012-365x(03)00161-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Thenge, J. D., B. Surendranath Reddy, and Rupali S. Jain. "Contribution to Soft Graph and Soft Tree." New Mathematics and Natural Computation 15, no. 01 (December 25, 2018): 129–43. http://dx.doi.org/10.1142/s179300571950008x.

Full text

Abstract:

Soft set theory introduced by D. Molodstov is a new theory which deals with uncertainty. Connected graphs can be represented by using soft sets called soft graphs. In the present paper, we introduce the tabular representation of soft graph and define radius, diameter, center and degree of soft graph. We also define union, product of soft graphs and soft trees. We then derive some properties of radius, degree of vertex in soft graph and soft trees.

APA, Harvard, Vancouver, ISO, and other styles

3

Козневски and E. Kozniewski. "Roof Skeletons and Graph Theory Trees." Geometry & Graphics 4, no. 1 (March 17, 2016): 12–20. http://dx.doi.org/10.12737/18054.

Full text

Abstract:

The problem of constructing roofs of many papers [1; 6; 7; 9; etc.]. In this case, some studies suggested to use a computer and special programs [10; 13; 16; etc.]. The geometry of the efficient design of roofs is actual scientific direction, so in the educational process of architectural and building trades made corresponding innovations [2; 8; 14; 15; 17–20; etc.]. The roofs considered in this article are defined as special geometric polyhedral surfaces, on the basis of two assumptions: (1) all eaves of a roof form a planar (simply-connected or k-connected) polygon called the base, (2) every hipped roof end makes the same slope angle with the (horizontal) plane which contains the base. All the vertices and edges of such a roof, forming the roof skeleton, determine a graph. The orthogonal projection of a roof skeleton onto the base plane leads to a planar graph. On the basis of [11] and [12] and continuing the investigations for regular roofs, we formulate further properties which enable studying the shapes of the roofs spread over simply connected v-gons for an arbitrary integer v (v ≥ 3). We also introduce new operations: splitting and grafting of graphs, and formulate some properties of these operations. By means of such operations, the creation of a graph with cycles using two or more trees is possible. In particular, the operation of the grafting of a roof allows modeling an atrial roof.

APA, Harvard, Vancouver, ISO, and other styles

4

Janson, Svante. "Random trees in a graph and trees in a random graph." Mathematical Proceedings of the Cambridge Philosophical Society 100, no. 2 (September 1986): 319–30. http://dx.doi.org/10.1017/s0305004100066111.

Full text

Abstract:

This paper treats two related sets of problems in the theory of random graphs. In Sections 2 and 3 we study random spanning subtrees of a complete graph (or, equivalently, random labelled trees). It is shown that the number of common edges of two such random trees asymptotically has a Poisson distribution with expectation 2. Similar results are obtained for the number of edges in the intersection or union of more than two random trees.

APA, Harvard, Vancouver, ISO, and other styles

5

Markhabatov, Nurlan. "Approximations of Acyclic Graphs." Bulletin of Irkutsk State University. Series Mathematics 40 (2022): 104–11. http://dx.doi.org/10.26516/1997-7670.2022.40.104.

Full text

Abstract:

In this paper, approximations of acyclic graphs are studied. It is proved that any theory of an acyclic graph (tree) of finite diameter is pseudofinite with respect to acyclic graphs (trees), that is, any such theory is approximated by theories of finite structures (acyclic graphs, trees). It is also proved that an acyclic graph of infinite diameter with infinite number of rays is pseudofinite.

APA, Harvard, Vancouver, ISO, and other styles

6

Zeen El Deen, Mohamed R. "Enumeration of spanning trees in prisms of some graphs." Proyecciones (Antofagasta) 42, no. 2 (December 1, 2023): 339–91. http://dx.doi.org/10.22199/issn.0717-6279-4664.

Full text

Abstract:

In graph theory, a prism over a graph G is the cartesian product of the graph G with P₂. The purpose of this work is to investigate the complexity of the prisms of some path and cycle-related graphs. In particular, we obtain simpler and more explicit formulas for the complexity of a special class of prisms of path-related graphs: fan graph, ladder graph, the composition Pn[P₂] graph, and book graph. Moreover, we obtain straightforward formulas for the complexity of a special class of prisms of cycle-related graphs: wheel graph, gear graph, prism graph, n−crossed prism graph, mirror graph M(Cn) of even cycle Cn, twisted prism, total graph T(Cn) of the cycle Cn, the friendship graph, the flower graph, and planner sunflower graph. These closed formulas are deduced using some basic properties of block matrix, recurrence relation, eigenvalues of circulant matrices, and orthogonal polynomials.

APA, Harvard, Vancouver, ISO, and other styles

7

JOHANNSEN, DANIEL, MICHAEL KRIVELEVICH, and WOJCIECH SAMOTIJ. "Expanders Are Universal for the Class of All Spanning Trees." Combinatorics, Probability and Computing 22, no. 2 (January 3, 2013): 253–81. http://dx.doi.org/10.1017/s0963548312000533.

Full text

Abstract:

A graph is calleduniversalfor a given graph class(or, equivalently,-universal) if it contains a copy of every graph inas a subgraph. The construction of sparse universal graphs for various classeshas received a considerable amount of attention. There is particular interest in tight-universal graphs, that is, graphs whose number of vertices is equal to the largest number of vertices in a graph from. Arguably, the most studied case is that whenis some class of trees. In this work, we are interested in(n,Δ), the class of alln-vertex trees with maximum degree at most Δ. We show that everyn-vertex graph satisfying certain natural expansion properties is(n,Δ)-universal. Our methods also apply to the case when Δ is some function ofn. Since random graphs are known to be good expanders, our result implies, in particular, that there exists a positive constantcsuch that the random graphG(n,cn−1/3log2n) is asymptotically almost surely (a.a.s.) universal for(n,O(1)). Moreover, a corresponding result holds for the random regular graph of degreecn2/3log2n. Another interesting consequence is the existence of locally sparsen-vertex(n,Δ)-universal graphs. For example, we show that one can (randomly) constructn-vertex(n,O(1))-universal graphs with clique number at most five. This complements the construction of Bhatt, Chung, Leighton and Rosenberg (1989), whose(n,Δ)-universal graphs with merelyO(n)edges contain large cliques of size Ω(Δ). Finally, we show that random graphs are robustly(n,Δ)-universal in the context of the Maker–Breaker tree-universality game.

APA, Harvard, Vancouver, ISO, and other styles

8

Raczek, Joanna, and Rita Zuazua. "Progress on Roman and Weakly Connected Roman Graphs." Mathematics 9, no. 16 (August 5, 2021): 1846. http://dx.doi.org/10.3390/math9161846.

Full text

Abstract:

A graph G for which γR(G)=2γ(G) is the Roman graph, and if γRwc(G)=2γwc(G), then G is the weakly connected Roman graph. In this paper, we show that the decision problem of whether a bipartite graph is Roman is a co-NP-hard problem. Next, we prove similar results for weakly connected Roman graphs. We also study Roman trees improving the result of M.A. Henning’s A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002). Moreover, we give a characterization of weakly connected Roman trees.

APA, Harvard, Vancouver, ISO, and other styles

9

Finbow, Stephen, and Christopher M. van Bommel. "γ-Graphs of Trees." Algorithms 12, no. 8 (July 30, 2019): 153. http://dx.doi.org/10.3390/a12080153.

Full text

Abstract:

For a graph G = ( V , E ) , the γ -graph of G, denoted G ( γ ) = ( V ( γ ) , E ( γ ) ) , is the graph whose vertex set is the collection of minimum dominating sets, or γ -sets of G, and two γ -sets are adjacent in G ( γ ) if they differ by a single vertex and the two different vertices are adjacent in G. In this paper, we consider γ -graphs of trees. We develop an algorithm for determining the γ -graph of a tree, characterize which trees are γ -graphs of trees, and further comment on the structure of γ -graphs of trees and its connections with Cartesian product graphs, the set of graphs which can be obtained from the Cartesian product of graphs of order at least two.

APA, Harvard, Vancouver, ISO, and other styles

10

NATH, MILAN, and SOMNATH PAUL. "GRAPH TRANSFORMATION AND DISTANCE SPECTRAL RADIUS." Discrete Mathematics, Algorithms and Applications 05, no. 03 (September 2013): 1350014. http://dx.doi.org/10.1142/s1793830913500146.

Full text

Abstract:

Trees are very common in the theory and applications of combinatorics. In this paper, we consider graphs whose underlying structure is a tree and study the behavior of the distance spectral radius under a graph transformation. As an application, we find the corona tree that maximizes the distance spectral radius among all corona trees with a fixed maximum degree. We also find the graph with minimal (maximal) distance spectral radius among all corona trees. Finally, we determine the graph with minimal distance spectral radius in a special class of corona trees.

APA, Harvard, Vancouver, ISO, and other styles

11

El-Mesady, A., Omar Bazighifan, and S. S. Askar. "A Novel Approach for Cyclic Decompositions of Balanced Complete Bipartite Graphs into Infinite Graph Classes." Journal of Function Spaces 2022 (May 4, 2022): 1–12. http://dx.doi.org/10.1155/2022/9308708.

Full text

Abstract:

Graph theory is considered an attractive field for finding the proof techniques in discrete mathematics. The results of graph theory have applications in many areas of social, computing, and natural sciences. Graph labelings and decompositions have received much attention in the literature. Several types of graph labeling were proposed for solving the problem of decomposing different graph classes. In the present paper, we propose a technique for labeling the vertices of a bipartite graph G with n edges, called orthogonal labeling, to yield cyclic decompositions of balanced complete bipartite graphs K n , n by the graph G . By applying the proposed orthogonal labeling technique, we had constructed decompositions of K n , n by paths, trees, one factorization, disjoint union of cycles, complete bipartite graphs, disjoint union of trees, caterpillars, and so forth. From the constructed results, we can confirm that the proposed orthogonal labeling technique is effective.

APA, Harvard, Vancouver, ISO, and other styles

12

Simonet, Geneviève, and Anne Berry. "Properties and Recognition of Atom Graphs." Algorithms 15, no. 8 (August 19, 2022): 294. http://dx.doi.org/10.3390/a15080294.

Full text

Abstract:

The atom graph of a connected graph is a graph whose vertices are the atoms obtained by clique minimal separator decomposition of this graph, and whose edges are the edges of all its atom trees. A graph G is an atom graph if there is a graph whose atom graph is isomorphic to G. We study the class of atom graphs, which is also the class of atom graphs of chordal graphs, and the associated recognition problem. We prove that each atom graph is a perfect graph and give a characterization of atom graphs in terms of a spanning tree, inspired by the characterization of clique graphs of chordal graphs as expanded trees. We also characterize the chordal graphs having the same atom and clique graph, and solve the recognition problem of atom graphs of two graph classes.

APA, Harvard, Vancouver, ISO, and other styles

13

Hosamani, S. M., V. B. Awati, and R. M. Honmore. "On graphs with equal dominating and c-dominating energy." Applied Mathematics and Nonlinear Sciences 4, no. 2 (December 24, 2019): 503–12. http://dx.doi.org/10.2478/amns.2019.2.00047.

Full text

Abstract:

AbstractGraph energy and domination in graphs are most studied areas of graph theory. In this paper we try to connect these two areas of graph theory by introducing c-dominating energy of a graph G. First, we show the chemical applications of c-dominating energy with the help of well known statistical tools. Next, we obtain mathematical properties of c-dominating energy. Finally, we characterize trees, unicyclic graphs, cubic and block graphs with equal dominating and c-dominating energy.

APA, Harvard, Vancouver, ISO, and other styles

14

Zuki, Wan Nor Nabila Nadia Wan, Zhibin Du, Muhammad Kamran Jamil, and Roslan Hasni. "Extremal Trees with Respect to the Difference between Atom-Bond Connectivity Index and Randić Index." Symmetry 12, no. 10 (September 25, 2020): 1591. http://dx.doi.org/10.3390/sym12101591.

Full text

Abstract:

Let G be a simple, connected and undirected graph. The atom-bond connectivity index (ABC(G)) and Randić index (R(G)) are the two most well known topological indices. Recently, Ali and Du (2017) introduced the difference between atom-bond connectivity and Randić indices, denoted as ABC−R index. In this paper, we determine the fourth, the fifth and the sixth maximum chemical trees values of ABC−R for chemical trees, and characterize the corresponding extremal graphs. We also obtain an upper bound for ABC−R index of such trees with given number of pendant vertices. The role of symmetry has great importance in different areas of graph theory especially in chemical graph theory.

APA, Harvard, Vancouver, ISO, and other styles

15

KIYOMI, MASASHI, TOSHIKI SAITOH, and RYUHEI UEHARA. "BIPARTITE PERMUTATION GRAPHS ARE RECONSTRUCTIBLE." Discrete Mathematics, Algorithms and Applications 04, no. 03 (August 6, 2012): 1250039. http://dx.doi.org/10.1142/s1793830912500395.

Full text

Abstract:

The graph reconstruction conjecture is a long-standing open problem in graph theory. The conjecture has been verified for all graphs with at most 11 vertices. Further, the conjecture has been verified for regular graphs, trees, disconnected graphs, unit interval graphs, separable graphs with no pendant vertex, outer-planar graphs, and unicyclic graphs. We extend the list of graph classes for which the conjecture holds. We give a proof that bipartite permutation graphs are reconstructible.

APA, Harvard, Vancouver, ISO, and other styles

16

Jahanbani, Akbar, Hajar Shooshtari, and Yilun Shang. "Extremal trees for the Randić index." Acta Universitatis Sapientiae, Mathematica 14, no. 2 (December 1, 2022): 239–49. http://dx.doi.org/10.2478/ausm-2022-0016.

Full text

Abstract:

Abstract Graph theory has applications in various fields due to offering important tools such as topological indices. Among the topological indices, the Randić index is simple and of great importance. The Randić index of a graph 𝒢 can be expressed as R ( G ) = ∑ x y ∈ Y ( G ) 1 τ ( x ) τ ( y ) R\left( G \right) = \sum\nolimits_{xy \in Y\left( G \right)} {{1 \over {\sqrt {\tau \left( x \right)\tau \left( y \right)} }}} , where 𝒴(𝒢) represents the edge set and τ(x) is the degree of vertex x. In this paper, considering the importance of the Randić index and applications two-trees graphs, we determine the first two minimums among the two-trees graphs.

APA, Harvard, Vancouver, ISO, and other styles

17

Panda, Swarup, and Dr Sukanta Pati. "On The Inverse Of A Class Of Bipartite Graphs With Unique Perfect Matchings." Electronic Journal of Linear Algebra 29 (September 20, 2015): 89–101. http://dx.doi.org/10.13001/1081-3810.2865.

Full text

Abstract:

Let G be a simple, undirected graph and Gw be the weighted graph obtained from G by giving weights to its edges using a positive weight function w. A weighted graph Gw is said to be nonsingular if its adjacency matrix A(Gw) is nonsingular. In [9], Godsil has given a class $\mathcal{G }$of connected, unweighted, bipartite, nonsingular graphs G with a unique perfect matching, such that A(G)â1 is signature similar to a nonnegative matrix, that is, there exists a diagonal matrix D with diagonal entries Â±1 such that DA(G)â1D is nonnegative. The graph associated to the matrix DA(G)â1D is called the inverse of G and it is denoted by G+. The graph G+ is an undirected, weighted, connected, bipartite graph with a unique perfect matching. Nonsingular, unweighted trees are contained inside the class G. We first give a constructive characterization of the class of weighted graphs Hw that can occur as the inverse of some graph Gâ\mathcal{ G}. This generalizes Theorem 2.6 of Neumann and Pati[13], where the authors have characterized graphs that occur as inverses of nonsingular, unweighted trees. A weighted graph Gw is said to have the property (R) if for each eigenvalue Î» of A(Gw), 1âÎ» is also an eigenvalue of A(Gw). If further, the multiplicity of Î» and 1âÎ» are the same, then Gw is said to have property (SR). A characterization of the class of nonsingular, weighted trees Tw with at least 8 vertices that have property (R) was given in [13] under some restriction on the weights. It is natural to ask for such a characterization for the whole of G, possibly with some weaker restrictions on the weights. We supply such a characterization. In particular, for trees it settles an open problem raised in [13].

APA, Harvard, Vancouver, ISO, and other styles

18

Boaventura-Netto, Paulo Oswaldo. "Ranking graph edges by the weight of their spanning arborescences or trees." Pesquisa Operacional 28, no. 1 (April 2008): 59–73. http://dx.doi.org/10.1590/s0101-74382008000100004.

Full text

Abstract:

A result based on a classic theorem of graph theory is generalized for edge-valued graphs, allowing determination of the total value of the spanning arborescences with a given root and containing a given arc in a directed valued graph. A corresponding result for undirected valued graphs is also presented. In both cases, the technique allows for a ranking of the graph edges by importance under this criterion. This ranking is proposed as a tool to determine the relative importance of the edges of a graph in network vulnerability studies. Some examples of application are presented.

APA, Harvard, Vancouver, ISO, and other styles

19

Li, Feng. "The Number of Spanning Trees in the Composition Graphs." Mathematical Problems in Engineering 2014 (2014): 1–5. http://dx.doi.org/10.1155/2014/613685.

Full text

Abstract:

Using the composition of some existing smaller graphs to construct some large graphs, the number of spanning trees and the Laplacian eigenvalues of such large graphs are also closely related to those of the corresponding smaller ones. By using tools from linear algebra and matrix theory, we establish closed formulae for the number of spanning trees of the composition of two graphs with one of them being an arbitrary complete 3-partite graph and the other being an arbitrary graph. Our results extend some of the previous work, which depend on the structural parameters such as the number of vertices and eigenvalues of the small graphs only.

APA, Harvard, Vancouver, ISO, and other styles

20

Courcelle, Bruno. "Unfoldings and Coverings of Weighted Graphs." Fundamenta Informaticae 189, no. 1 (July 7, 2023): 1–47. http://dx.doi.org/10.3233/fi-222150.

Full text

Abstract:

Coverings of undirected graphs are used in distributed computing, and unfoldings of directed graphs in semantics of programs. We study these two notions from a graph theoretical point of view so as to highlight their similarities, as they are both defined in terms of surjective graph homomorphisms. In particular, universal coverings and complete unfoldings are infinite trees that are regular if the initial graphs are finite. Regularity means that a tree has finitely many subtrees up to isomorphism. Two important theorems have been established by Leighton and Norris for coverings of finite graphs. We prove similar results for unfoldings of finite directed graphs. Moreover, we generalize coverings and similarly, unfoldings to graphs and digraphs equipped with finite or infinite weights attached to edges of the covered or unfolded graphs. This generalization yields a canonical “factorization” of the universal covering of any finite graph, that (provably) does not exist without using weights. Introducing ω as an infinite weight provides us with finite descriptions of regular trees having nodes of countably infinite degree. Regular trees (trees having finitely many subtrees up to isomorphism) play an important role in the extension of Formal Language Theory to infinite structures described in finitary ways. Our weighted graphs offer effective descriptions of the above mentioned regular trees and yield decidability results. We also generalize to weighted graphs and their coverings a classical factorization theorem of their characteristic polynomials.

APA, Harvard, Vancouver, ISO, and other styles

21

Al-Janabi, H., and G. Bacsó. "Sanskruti Index of some Chemical Trees and Unicyclic Graphs." Journal of Physics: Conference Series 2287, no. 1 (June 1, 2022): 012005. http://dx.doi.org/10.1088/1742-6596/2287/1/012005.

Full text

Abstract:

Abstract In chemical graph theory, topological indices are used to estimate the bio-activity of chemical compounds. The molecular graph models molecular compounds. A molecular graph represents the structural formula of a chemical compound relative to the graph. Its vertices represent the atoms of the compound, and its edges represent the chemical bonds. In 2017, Hosamani introduced the Sanskruti index S(G) and defined it as S(G) = Σuv∈E(G) ((δu ⋅ δv)/(δu + δv − 2))3, where δu is the sum of the degrees of all neighbors of the vertex u in G. The Sanskruti index displays a good connection with an entropy of octane isomers. In this paper, the Sanskruti index S(G) is computed for some chemical trees and unicyclic graphs.

APA, Harvard, Vancouver, ISO, and other styles

22

Arockiaraj, Micheal, J. Nancy Delaila, and Jessie Abraham. "Optimal Wirelength of Balanced Complete Multipartite Graphs onto Cartesian Product of {Path, Cycle} and Trees." Fundamenta Informaticae 178, no. 3 (January 15, 2021): 187–202. http://dx.doi.org/10.3233/fi-2021-2003.

Full text

Abstract:

In any interconnection network, task allocation plays a major role in the processor speed as fair distribution leads to enhanced performance. Complete multipartite networks serve well for this purpose as the task can be split into different partites which improves the degree of reliability of the network. Such an allocation process in the network can be done by means of graph embedding. The optimal wirelength of a graph embedding helps in the distribution of deterministic algorithms from the guest graph to other host graphs in order to incorporate its unique deterministic properties on that chosen graph. In this paper, we propose an algorithm to compute the optimal wirelength of balanced complete multipartite graphs onto the Cartesian product of trees with path and cycle. Moreover, we derive the closed formulae for wirelengths in specific trees like (1-rooted) complete binary tree and sibling graphs.

APA, Harvard, Vancouver, ISO, and other styles

23

Manjula, V. "Graph Applications to Data Structures." Advanced Materials Research 433-440 (January 2012): 3297–301. http://dx.doi.org/10.4028/www.scientific.net/amr.433-440.3297.

Full text

Abstract:

This paper presents a topic on Graph theory and its application to data Structures which I consider basic and useful to students in APPLIED MATHEMATICS and ENGINEERING.This paper gives an elementary introduction of Graph theory and its application to data structures. Elements of Graph theory are indispensable in almost all computer Science areas .It can be used in Some areas such as syntactic analysis, fault detection, diagnosis in computers and minimal path problems. The computer representation and manipulation of graph are also discussed so that certain algorithms can be included .A major theme of this paper is to study Graph theory and its Application to data structures Furthermore I hope the students not only learn the course but also develop their analogy perceive, formulate and to solve mathematical programs Thus Graphs especially trees, binary trees are used widely in the representation of data structures this course one can develop mathematical maturity, ability to understand and create mathematical argumentsMethod of derivation is procedure given in the text books with necessary formulae and their application . Concepts and notations from discrete mathematics are useful in studying and describing objects and problems in branches of computer science, such as computer algorithms, programming languages.

APA, Harvard, Vancouver, ISO, and other styles

24

Zeen El Deen, Mohamed R., Walaa A. Aboamer, and Hamed M. El-Sherbiny. "The Complexity of the Super Subdivision of Cycle-Related Graphs Using Block Matrices." Computation 11, no. 8 (August 15, 2023): 162. http://dx.doi.org/10.3390/computation11080162.

Full text

Abstract:

The complexity (number of spanning trees) in a finite graph Γ (network) is crucial. The quantity of spanning trees is a fundamental indicator for assessing the dependability of a network. The best and most dependable network is the one with the most spanning trees. In graph theory, one constantly strives to create novel structures from existing ones. The super subdivision operation produces more complicated networks, and the matrices of these networks can be divided into block matrices. Using methods from linear algebra and the characteristics of block matrices, we derive explicit formulas for determining the complexity of the super subdivision of a certain family of graphs, including the cycle Cn, where n=3,4,5,6; the dumbbell graph Dbm,n; the dragon graph Pm(Cn); the prism graph Πn, where n=3,4; the cycle Cn with a Pn2-chord, where n=4,6; and the complete graph K4. Additionally, 3D plots that were created using our results serve as illustrations.

APA, Harvard, Vancouver, ISO, and other styles

25

Ramanujam, R., and Ramanathan S. Thinniyam. "Definability in first-order theories of graph orderings ⋆." Journal of Logic and Computation 30, no. 1 (January 2020): 403–20. http://dx.doi.org/10.1093/logcom/exaa017.

Full text

Abstract:

Abstract We study definability in the first-order theory of graph order: i.e. the set of all isomorphism types of simple finite graphs ordered by either the minor, subgraph or induced subgraph relation. Natural graph families like cycles and trees are definable in these orders, as also notions like connectivity, maximum degree, etc. This machinery allows us to show mutual interpretability with arithmetic for all orders. We discuss implications for formalizing statements of graph theory in such theories of order. 1

APA, Harvard, Vancouver, ISO, and other styles

26

Wang, Shaohui, and Bing Wei. "Multiplicative Zagreb indices of cacti." Discrete Mathematics, Algorithms and Applications 08, no. 03 (August 2016): 1650040. http://dx.doi.org/10.1142/s1793830916500403.

Full text

Abstract:

Let [Formula: see text] be multiplicative Zagreb index of a graph [Formula: see text]. A connected graph is a cactus graph if and only if any two of its cycles have at most one vertex in common, which is a generalization of trees and has been the interest of researchers in the field of material chemistry and graph theory. In this paper, we use a new tool to obtain the upper and lower bounds of [Formula: see text] for all cactus graphs and characterize the corresponding extremal graphs.

APA, Harvard, Vancouver, ISO, and other styles

27

Manimuthu, Yamuna, and Karthika Kumarasamy. "A Survey on Characterizing Trees Using Domination Number." Mathematics 10, no. 13 (June 22, 2022): 2173. http://dx.doi.org/10.3390/math10132173.

Full text

Abstract:

Ever since the discovery of domination numbers by Claude Berge in the year 1958, graph domination has become an important domain in graph theory that has strengthened itself as a theory and has extended its contributions to various applications. Tree characterization is an important problem in graph domination. This survey focuses on presenting a collection of results on characterizing trees using domination number.

APA, Harvard, Vancouver, ISO, and other styles

28

Niwanthi, Wan. "Solving sweeping problem for trees in graph theory." Computer Science and Mathematical Modelling, no. 17/2023 (January 30, 2024): 29–33. http://dx.doi.org/10.5604/01.3001.0054.6288.

Full text

Abstract:

We develop a theory to determine the search number of a graph that allows us to detect an intruder along an edge without limiting the visibility of adjacent vertices. The presented technique here will allow to express the sweep problem as a linear program using an existing formulation of a linear program designed for problems where capture occurs only at a vertex of a graph. We also provide a method to solve the sweep problem for any complex tree, utilizing a set of sub-trees of the tree.

APA, Harvard, Vancouver, ISO, and other styles

29

Hu, Yarong, and Qiongxiang Huang. "Quadratic Starlike Trees." Algebra Colloquium 30, no. 04 (November 28, 2023): 615–38. http://dx.doi.org/10.1142/s1005386723000470.

Full text

Abstract:

We introduce the notion of a quadratic graph, which is a graph whose eigenvalues are integral or quadratic algebraic integral, and we determine nine infinite families of quadratic starlike trees, which are just all the quadratic starlike trees including integral starlike trees. Thus, the quadratic starlike trees are completely characterized. The expressions for characteristic polynomials of quadratic starlike trees are also given.

APA, Harvard, Vancouver, ISO, and other styles

30

PANDA, SWARUP. "Inverses of bicyclic graphs." Electronic Journal of Linear Algebra 32 (February 6, 2017): 217–31. http://dx.doi.org/10.13001/1081-3810.3322.

Full text

Abstract:

A graph G is said to be nonsingular (resp., singular) if its adjacency matrix A(G) is nonsingular (resp., singular). The inverse of a nonsingular graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A(G) via a diagonal matrix of Â±1s. Consider connected bipartite graphs with unique perfect matchings such that the graph obtained by contracting all matching edges is also bipartite. In [C.D. Godsil. Inverses of trees. Combinatorica, 5(1):33â39, 1985.], Godsil proved that such graphs are invertible. He posed the question of characterizing the bipartite graphs with unique perfect matchings possessing inverses. In this article, Godsilâs question for the class of bicyclic graphs is answered.

APA, Harvard, Vancouver, ISO, and other styles

31

Knor, Martin, Muhammad Imran, Muhammad Kamran Jamil, and Riste Škrekovski. "Remarks on Distance Based Topological Indices for ℓ-Apex Trees." Symmetry 12, no. 5 (May 12, 2020): 802. http://dx.doi.org/10.3390/sym12050802.

Full text

Abstract:

A graph G is called an ℓ-apex tree if there exist a vertex subset A ⊂ V ( G ) with cardinality ℓ such that G − A is a tree and there is no other subset of smaller cardinality with this property. In the paper, we investigate extremal values of several monotonic distance-based topological indices for this class of graphs, namely generalized Wiener index, and consequently for the Wiener index and the Harary index, and also for some newer indices as connective eccentricity index, generalized degree distance, and others. For the one extreme value we obtain that the extremal graph is a join of a tree and a clique. Regarding the other extreme value, which turns out to be a harder problem, we obtain results for ℓ = 1 and pose some open questions for higher ℓ. Symmetry has always played an important role in Graph Theory, in recent years, this role has increased significantly in several branches of this field, including topological indices of graphs.

APA, Harvard, Vancouver, ISO, and other styles

32

FRATI, FABRIZIO. "ON MINIMUM AREA PLANAR UPWARD DRAWINGS OF DIRECTED TREES AND OTHER FAMILIES OF DIRECTED ACYCLIC GRAPHS." International Journal of Computational Geometry & Applications 18, no. 03 (June 2008): 251–71. http://dx.doi.org/10.1142/s021819590800260x.

Full text

Abstract:

It has been shown that there exist planar digraphs that require exponential area in every upward straight-line planar drawing. On the other hand, upward poly-line planar drawings of planar graphs can be realized in Θ(n2) area. In this paper we consider families of DAGs that naturally arise in practice, like DAGs whose underlying graph is a tree (directed trees), is a bipartite graph (directed bipartite graphs), or is an outerplanar graph (directed outerplanar graphs). Concerning directed trees, we show that optimal Θ(n log n) area upward straight-line/poly-line planar drawings can be constructed. However, we prove that if the order of the neighbors of each node is assigned, then exponential area is required for straight-line upward drawings and quadratic area is required for poly-line upward drawings, results surprisingly and sharply contrasting with the area bounds for planar upward drawings of undirected trees. After having established tight bounds on the area requirements of planar upward drawings of several families of directed trees, we show how the results obtained for trees can be exploited to determine asymptotic optimal values for the area occupation of planar upward drawings of directed bipartite graphs and directed outerplanar graphs.

APA, Harvard, Vancouver, ISO, and other styles

33

Berry, Anne, and Geneviève Simonet. "Computing the Atom Graph of a Graph and the Union Join Graph of a Hypergraph." Algorithms 14, no. 12 (November 28, 2021): 347. http://dx.doi.org/10.3390/a14120347.

Full text

Abstract:

The atom graph of a graph is a graph whose vertices are the atoms obtained by clique minimal separator decomposition of this graph, and whose edges are the edges of all possible atom trees of this graph. We provide two efficient algorithms for computing this atom graph, with a complexity in O(min(nωlogn,nm,n(n+m¯)) time, where n is the number of vertices of G, m is the number of its edges, m¯ is the number of edges of the complement of G, and ω, also denoted by α in the literature, is a real number, such that O(nω) is the best known time complexity for matrix multiplication, whose current value is 2,3728596. This time complexity is no more than the time complexity of computing the atoms in the general case. We extend our results to α-acyclic hypergraphs, which are hypergraphs having at least one join tree, a join tree of an hypergraph being defined by its hyperedges in the same way as an atom tree of a graph is defined by its atoms. We introduce the notion of union join graph, which is the union of all possible join trees; we apply our algorithms for atom graphs to efficiently compute union join graphs.

APA, Harvard, Vancouver, ISO, and other styles

34

Liu, Yuqing, and Nicholas A. Scoville. "The Realization Problem for Discrete Morse Functions on Trees." Algebra Colloquium 27, no. 03 (August 27, 2020): 455–68. http://dx.doi.org/10.1142/s1005386720000371.

Full text

Abstract:

We introduce a new notion of equivalence of discrete Morse functions on graphs called persistence equivalence. Two functions are considered persistence equivalent if and only if they induce the same persistence diagram. We compare this notion of equivalence to other notions of equivalent discrete Morse functions. Then we compute an upper bound for the number of persistence equivalent discrete Morse functions on a fixed graph and show that this upper bound is sharp in the case where our graph is a tree. This is a version of the “realization problem” of the persistence map. We conclude with an example illustrating our construction.

APA, Harvard, Vancouver, ISO, and other styles

35

DARMANN, ANDREAS. "POPULAR SPANNING TREES." International Journal of Foundations of Computer Science 24, no. 05 (August 2013): 655–77. http://dx.doi.org/10.1142/s0129054113500226.

Full text

Abstract:

Combinatorial Optimization is combined with Social Choice Theory when the goal is to decide on the quality of a spanning tree of an undirected graph. Given individual preferences over the edges of the graph, spanning trees are compared by means of a Condorcet criterion. The comparisons are based on scoring functions used in classic voting rules such as approval voting and Borda voting. In this work, we investigate the computational complexity involved in deciding on the quality of a spanning tree with respect to the different voting rules adapted. In particular, we draw the sharp separation line between polynomially solvable and computationally intractable instances.

APA, Harvard, Vancouver, ISO, and other styles

36

Lehtonen, Erkko, and Tamás Waldhauser. "Associative spectra of graph algebras I." Journal of Algebraic Combinatorics 53, no. 3 (May 2021): 613–38. http://dx.doi.org/10.1007/s10801-020-01010-w.

Full text

Abstract:

AbstractAssociative spectra of graph algebras are examined with the help of homomorphisms of DFS trees. Undirected graphs are classified according to the associative spectra of their graph algebras; there are only three distinct possibilities: constant 1, powers of 2, and Catalan numbers. Associative and antiassociative digraphs are described, and associative spectra are determined for certain families of digraphs, such as paths, cycles, and graphs on two vertices.

APA, Harvard, Vancouver, ISO, and other styles

37

Tang, Liang Wen, Juan Liu, and Shuangwei Qin. "Construction of Equienergetic Trees." Match Communications in Mathematical and in Computer Chemistry 91, no. 2 (October 2023): 485–88. http://dx.doi.org/10.46793/match.91-2.485t.

Full text

Abstract:

The energy E(G) of a graph G is the sum of the absolute values of all eigenvalues of G. Two graphs of the same order are said to be equienergetic if their energies are equal. As pointed out by Gutman, it is not known how to systematically construct any pair of equienergetic, non-cospectral trees until now. Inspired by the research of integral trees, we proposed a construction of infinite pairs of equienergetic trees of diameter 4.

APA, Harvard, Vancouver, ISO, and other styles

38

Kuhlmann, Marco, and Stephan Oepen. "Towards a Catalogue of Linguistic Graph Banks." Computational Linguistics 42, no. 4 (December 2016): 819–27. http://dx.doi.org/10.1162/coli_a_00268.

Full text

Abstract:

Graphs exceeding the formal complexity of rooted trees are of growing relevance to much NLP research. Although formally well understood in graph theory, there is substantial variation in the types of linguistic graphs, as well as in the interpretation of various structural properties. To provide a common terminology and transparent statistics across different collections of graphs in NLP, we propose to establish a shared community resource with an open-source reference implementation for common statistics.

APA, Harvard, Vancouver, ISO, and other styles

39

Shang, Yilun. "On the number of spanning trees, the Laplacian eigenvalues, and the Laplacian Estrada index of subdivided-line graphs." Open Mathematics 14, no. 1 (January 1, 2016): 641–48. http://dx.doi.org/10.1515/math-2016-0055.

Full text

Abstract:

Abstract As a generalization of the Sierpiński-like graphs, the subdivided-line graph Г(G) of a simple connected graph G is defined to be the line graph of the barycentric subdivision of G. In this paper we obtain a closed-form formula for the enumeration of spanning trees in Г(G), employing the theory of electrical networks. We present bounds for the largest and second smallest Laplacian eigenvalues of Г(G) in terms of the maximum degree, the number of edges, and the first Zagreb index of G. In addition, we establish upper and lower bounds for the Laplacian Estrada index of Г(G) based on the vertex degrees of G. These bounds are also connected with the number of spanning trees in Г(G).

APA, Harvard, Vancouver, ISO, and other styles

40

Bhattacharya, Anushree, and Madhumangal Pal. "A Fuzzy Graph Theory Approach to the Facility Location Problem: A Case Study in the Indian Banking System." Mathematics 11, no. 13 (July 4, 2023): 2992. http://dx.doi.org/10.3390/math11132992.

Full text

Abstract:

A fuzzy graph G is stated to have a set of trees as its tree cover if all the vertices of G are in their union. The maximum weight tree in the tree cover is assumed to be the cost of a tree cover for a fuzzy graph. For an integer β>0, finding a set of trees to cover all the vertices of a graph with minimum cost and at most β number of spanning trees is known as the β-tree cover problem. Combining the tree-covering concept and facility location problem in a fuzzy environment for solving critical real-life problems in the recent era is a more fruitful approach. This issue strongly inspires us to develop a model with a practical algorithm. This paper provides an algorithm and complexity analysis to determine the number of rooted trees s covering the given fuzzy graph. In addition, a model is constructed with three optimization programming problems in the facility location problem and a tree covering fuzzy graphs. The model includes two types of the facility location problem, simultaneously addressing a variable covering radius and a fixed covering radius. A numerical example is provided to further describe the model, then, in the application part of the paper, the proposed model is applied to solve the real-life problem of maximizing demand saturation by minimizing the number of small denominations in the Indian banking system. This problem involves the data input of different indicators in the banking system along with details of the denominations of banknotes.

APA, Harvard, Vancouver, ISO, and other styles

41

Du, Zhibin. "The sum of the first two largest signless Laplacian eigenvalues of trees and unicyclic graphs." Electronic Journal of Linear Algebra 35 (February 1, 2019): 449–67. http://dx.doi.org/10.13001/1081-3810.3405.

Full text

Abstract:

Let $G$ be a graph on $n$ vertices with $e(G)$ edges. The sum of eigenvalues of graphs has been receiving a lot of attention these years. Let $S_2 (G)$ be the sum of the first two largest signless Laplacian eigenvalues of $G$, and define $f(G) = e (G) +3 - S_2 (G)$. Oliveira et al. (2015) conjectured that $f(G) \geqslant f(U_{n})$ with equality if and only if $G \cong U_n$, where $U_n$ is the $n$-vertex unicyclic graph obtained by attaching $n-3$ pendent vertices to a vertex of a triangle. In this paper, it is proved that $S_2(G) < e(G) + 3 -\frac{2}{n}$ when $G$ is a tree, or a unicyclic graph whose unique cycle is not a triangle. As a consequence, it is deduced that the conjecture proposed by Oliveira et al. is true for trees and unicyclic graphs whose unique cycle is not a triangle.

APA, Harvard, Vancouver, ISO, and other styles

42

MELLOR, BLAKE. "TREE DIAGRAMS FOR STRING LINKS." Journal of Knot Theory and Its Ramifications 15, no. 10 (December 2006): 1303–18. http://dx.doi.org/10.1142/s0218216506005159.

Full text

Abstract:

In previous work, the author defined the intersection graph of a chord diagram associated with a string link (as in the theory of finite type invariants). In this paper, we classify the trees which can be obtained as intersection graphs of string link diagrams.

APA, Harvard, Vancouver, ISO, and other styles

43

Vasconcellos, Jucele França de Alencar, Edson Norberto Cáceres, Henrique Mongelli, Siang Wun Song, Frank Dehne, and Jayme Luiz Szwarcfiter. "New BSP/CGM algorithms for spanning trees." International Journal of High Performance Computing Applications 33, no. 3 (October 14, 2018): 444–61. http://dx.doi.org/10.1177/1094342018803672.

Full text

Abstract:

Computing a spanning tree (ST) and a minimum ST (MST) of a graph are fundamental problems in graph theory and arise as a subproblem in many applications. In this article, we propose parallel algorithms to these problems. One of the steps of previous parallel MST algorithms relies on the heavy use of parallel list ranking which, though efficient in theory, is very time-consuming in practice. Using a different approach with a graph decomposition, we devised new parallel algorithms that do not make use of the list ranking procedure. We proved that our algorithms are correct, and for a graph [Formula: see text], [Formula: see text], and [Formula: see text], the algorithms can be executed on a Bulk Synchronous Parallel/Coarse Grained Multicomputer (BSP/CGM) model using [Formula: see text] communications rounds with [Formula: see text] computation time for each round. To show that our algorithms have good performance on real parallel machines, we have implemented them on graphics processing unit. The obtained speedups are competitive and showed that the BSP/CGM model is suitable for designing general purpose parallel algorithms.

APA, Harvard, Vancouver, ISO, and other styles

44

Dobrinen, Natasha. "The Ramsey theory of the universal homogeneous triangle-free graph." Journal of Mathematical Logic 20, no. 02 (January 28, 2020): 2050012. http://dx.doi.org/10.1142/s0219061320500129.

Full text

Abstract:

The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math. 38(1) (1971) 69–83] and denoted [Formula: see text], is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.[Formula: see text] , eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] and culminating in work of Sauer [Coloring subgraphs of the Rado graph, Combinatorica 26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica 26(2) (2006) 183–205], the Ramsey theory of [Formula: see text] had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin. 2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math. 185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph [Formula: see text], there is a finite number [Formula: see text] such that for any coloring of all copies of [Formula: see text] in [Formula: see text] into finitely many colors, there is a subgraph of [Formula: see text] which is again universal homogeneous triangle-free in which the coloring takes no more than [Formula: see text] colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code [Formula: see text] and the development of their Ramsey theory.

APA, Harvard, Vancouver, ISO, and other styles

45

Mete, Filiz, Serife Buyukkose, Ozlem Cakir, and Ummugulsum Candeger. "Graphic representation of open and distance education history." Global Journal of Information Technology: Emerging Technologies 7, no. 3 (December 24, 2017): 92–98. http://dx.doi.org/10.18844/gjit.v7i3.2831.

Full text

Abstract:

Nowadays, learning and instruction take place independent of time and space through the distance education system,wherein courses are conducted completely online through network technologies using interactive video -based instructional materials. This study examines the open and distance education system that was a part of the history of education in the Turkish republic first at universities, and then in high sch ools and secondary schools. It is aimed to narrate the history of open and distance education using graph theory trees in order to provide a better understanding of this process. Within this context, the project YAYÇEP may be mentioned. Historical developments can be narrated in a chronological order through graph theory trees, and this makes it possible to see the big picture. Open and distance education is discussed, historical information is given and, finally, a graph theory tree drawn using the graph theory is used to explain the topic.Keywords: Distance education, open education, graph theory, the history of distance education.

APA, Harvard, Vancouver, ISO, and other styles

46

TRALDI, LORENZO. "Weighted Interlace Polynomials." Combinatorics, Probability and Computing 19, no. 1 (August 10, 2009): 133–57. http://dx.doi.org/10.1017/s0963548309990381.

Full text

Abstract:

The interlace polynomials introduced by Arratia, Bollobás and Sorkin extend to invariants of graphs with vertex weights, and these weighted interlace polynomials have several novel properties. One novel property is a version of the fundamental three-term formulathat lacks the last term. It follows that interlace polynomial computations can be represented by binary trees rather than mixed binary–ternary trees. Binary computation trees provide a description ofq(G) that is analogous to the activities description of the Tutte polynomial. IfGis a tree or forest then these ‘algorithmic activities’ are associated with a certain kind of independent set inG. Three other novel properties are weighted pendant-twin reductions, which involve removing certain kinds of vertices from a graph and adjusting the weights of the remaining vertices in such a way that the interlace polynomials are unchanged. These reductions allow for smaller computation trees as they eliminate some branches. If a graph can be completely analysed using pendant-twin reductions, then its interlace polynomial can be calculated in polynomial time. An intuitively pleasing property is that graphs which can be constructed through graph substitutions have vertex-weighted interlace polynomials which can be obtained through algebraic substitutions.

APA, Harvard, Vancouver, ISO, and other styles

47

Das, Kinkar, and SHAOWEI SUN. "Extremal graph on normalized Laplacian spectral radius and energy." Electronic Journal of Linear Algebra 29 (September 20, 2015): 237–53. http://dx.doi.org/10.13001/1081-3810.3263.

Full text

Abstract:

Let $G=(V,\,E)$ be a simple graph of order $n$ and the normalized Laplacian eigenvalues $\rho_1\geq \rho_2\geq \cdots\geq\rho_{n-1}\geq \rho_n=0$. The normalized Laplacian energy (or Randi\'c energy) of $G$ without any isolated vertex is defined as $$RE(G)=\sum_{i=1}^{n}|\rho_i-1|.$$ In this paper, a lower bound on $\rho_1$ of connected graph $G$ ($G$ is not isomorphic to complete graph) is given and the extremal graphs (that is, the second minimal normalized Laplacian spectral radius of connected graphs) are characterized. Moreover, Nordhaus-Gaddum type results for $\rho_1$ are obtained. Recently, Gutman et al.~gave a conjecture on Randi\'c energy of connected graph [I. Gutman, B. Furtula, \c{S}. B. Bozkurt, On Randi\'c energy, Linear Algebra Appl. 442 (2014) 50--57]. Here this conjecture for starlike trees is proven.

APA, Harvard, Vancouver, ISO, and other styles

48

Göbel, Andreas, J. A. Gregor Lagodzinski, and Karen Seidel. "Counting Homomorphisms to Trees Modulo a Prime." ACM Transactions on Computation Theory 13, no. 3 (September 30, 2021): 1–33. http://dx.doi.org/10.1145/3460958.

Full text

Abstract:

Many important graph-theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular independent sets and colourings. In this article, we study the complexity of # p H OMS T O H , the problem of counting graph homomorphisms from an input graph to a graph H modulo a prime number p . Dyer and Greenhill proved a dichotomy stating that the tractability of non-modular counting graph homomorphisms depends on the structure of the target graph. Many intractable cases in non-modular counting become tractable in modular counting due to the common phenomenon of cancellation. In subsequent studies on counting modulo 2, however, the influence of the structure of H on the tractability was shown to persist, which yields similar dichotomies. Our main result states that for every tree H and every prime p the problem # p H OMS T O H is either polynomial time computable or # p P-complete. This relates to the conjecture of Faben and Jerrum stating that this dichotomy holds for every graph H when counting modulo 2. In contrast to previous results on modular counting, the tractable cases of # p H OMS T O H are essentially the same for all values of the modulo when H is a tree. To prove this result, we study the structural properties of a homomorphism. As an important interim result, our study yields a dichotomy for the problem of counting weighted independent sets in a bipartite graph modulo some prime p . These results are the first suggesting that such dichotomies hold not only for the modulo 2 case but also for the modular counting functions of all primes p .

APA, Harvard, Vancouver, ISO, and other styles

49

Domagalski, Rachel, and Sivaram Narayan. "Tree Cover Number and Maximum Semidefinite Nullity of Some Graph Classes." Electronic Journal of Linear Algebra 36, no. 36 (September 30, 2020): 678–93. http://dx.doi.org/10.13001/ela.2020.5319.

Full text

Abstract:

Let $G$ be a graph with a vertex set $V$ and an edge set $E$ consisting of unordered pairs of vertices. The tree cover number of $G$, denoted $\tau(G)$, is the minimum number of vertex disjoint simple trees occurring as induced subgraphs of $G$ that cover all the vertices of $G$. In this paper, the tree cover number of a line graph $\tau(L(G))$ is shown to be equal to the path number $\pi(G)$ of $G$. Also, the tree cover numbers of shadow graphs, corona and Cartesian product of two graphs are found. The graph parameter $\tau(G)$ is related to another graph parameter $M_+(G)$, called the maximum semidefinite nullity of $G$. Suppose $S_+(G,\mathbb{R})$ denotes the collection of positive semidefinite real symmetric matrices associated with a given graph $G$. Then $M_+(G)$ is the maximum nullity among all matrices in $S_+(G,\mathbb{R})$. It has been conjectured that $\tau(G)\leq M_+(G)$. The conjecture is shown to be true for graph classes considered in this work.

APA, Harvard, Vancouver, ISO, and other styles

50

Nandini, G. Kirithiga, R. Sundara Rajan, A. Arul Shantrinal, T. M. Rajalaxmi, Indra Rajasingh, and Krishnan Balasubramanian. "Topological and Thermodynamic Entropy Measures for COVID-19 Pandemic through Graph Theory." Symmetry 12, no. 12 (December 2, 2020): 1992. http://dx.doi.org/10.3390/sym12121992.

Full text

Abstract:

Severe acute respiratory syndrome coronavirus 2 (SARS-CoV-2) has caused the global pandemic, coronavirus disease-2019 (COVID-19) which has resulted in 60.4 million infections and 1.42 million deaths worldwide. Mathematical models as an integral part of artificial intelligence are designed for contact tracing, genetic network analysis for uncovering the biological evolution of the virus, understanding the underlying mechanisms of the observed disease dynamics, evaluating mitigation strategies, and predicting the COVID-19 pandemic dynamics. This paper describes mathematical techniques to exploit and understand the progression of the pandemic through a topological characterization of underlying graphs. We have obtained several topological indices for various graphs of biological interest such as pandemic trees, Cayley trees, Christmas trees, and the corona product of Christmas trees and paths. We have also obtained an analytical expression for the thermodynamic entropies of pandemic trees as a function of R0, the reproduction number, and the level of spread, using the nested wreath product groups. Our plots of entropy and logarithms of topological indices of pandemic trees accentuate the underlying severity of COVID-19 over the 1918 Spanish flu pandemic.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Trees (graph theory)'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles