Log in

Relevant bibliographies by topics / Tree graphs / Journal articles

To see the other types of publications on this topic, follow the link: Tree graphs.

Journal articles on the topic 'Tree graphs'

Author: Grafiati

Published: 4 June 2021

Last updated: 8 February 2022

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

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Tree graphs.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Mandal, Subhrangsu, and Arobinda Gupta. "Convergecast Tree on Temporal Graphs." International Journal of Foundations of Computer Science 31, no. 03 (April 2020): 385–409. http://dx.doi.org/10.1142/s012905412050015x.

Full text

Abstract:

Temporal graphs are useful tools to model dynamic network topologies found in many applications. In this paper, we address the problem of constructing a convergecast tree on temporal graphs for data collection in dynamic sensor networks. Two types of convergecast trees, bounded arrival time convergecast tree and minimum total arrival time convergecast tree are defined as useful structures for low delay data collection. An [Formula: see text] time centralized algorithm is proposed to construct a bounded arrival time convergecast tree, where [Formula: see text] is the number of nodes, [Formula: see text] is the number of edges, and [Formula: see text] is the lifetime of the given temporal graph. The algorithm presented is an offline algorithm and assumes that all information about change in the graph topology is known apriori. It is then shown that the problem of constructing a minimum total arrival time convergecast tree is NP-complete, and an [Formula: see text] time centralized, offline heuristic algorithm is proposed to address it. The heuristic algorithm is evaluated with experiments on four real life data sets.

APA, Harvard, Vancouver, ISO, and other styles

2

Guo, Haiyan, and Bo Zhou. "On the α-spectral radius of graphs." Applicable Analysis and Discrete Mathematics, no. 00 (2020): 22. http://dx.doi.org/10.2298/aadm180210022g.

Full text

Abstract:

For 0 ? ? ? 1, Nikiforov proposed to study the spectral properties of the family of matrices A?(G) = ?D(G)+(1 ? ?)A(G) of a graph G, where D(G) is the degree diagonal matrix and A(G) is the adjacency matrix of G. The ?-spectral radius of G is the largest eigenvalue of A?(G). For a graph with two pendant paths at a vertex or at two adjacent vertices, we prove results concerning the behavior of the ?-spectral radius under relocation of a pendant edge in a pendant path. We give upper bounds for the ?-spectral radius for unicyclic graphs G with maximum degree ? ? 2, connected irregular graphs with given maximum degree and some other graph parameters, and graphs with given domination number, respectively. We determine the unique tree with the second largest ?-spectral radius among trees, and the unique tree with the largest ?-spectral radius among trees with given diameter. We also determine the unique graphs so that the difference between the maximum degree and the ?-spectral radius is maximum among trees, unicyclic graphs and non-bipartite graphs, respectively.

APA, Harvard, Vancouver, ISO, and other styles

3

Hao, Long. "A Novel Algorithm Based on the Degree Tree for Graph Isomorphism." Advanced Materials Research 225-226 (April 2011): 417–21. http://dx.doi.org/10.4028/www.scientific.net/amr.225-226.417.

Full text

Abstract:

The graph isomorphism problem is to study the relationship between two graphs which seem to be different, but essentially identically. A novel algorithm based on the degree tree is proposed, where each node of the tree describes a given vertex and its neighboring information of a graph. Two vertexes in different graphs are regarded as mapping if the corresponding nodes and all their junior nodes are similar. Hence by comparing their degree trees, two graphs can be determined whether matching or not, and the mapping vertexes can be found. Experimental results show the approach’s performance.

APA, Harvard, Vancouver, ISO, and other styles

4

Bunke, H., and B. T. Messmer. "Recent Advances in Graph Matching." International Journal of Pattern Recognition and Artificial Intelligence 11, no. 01 (February 1997): 169–203. http://dx.doi.org/10.1142/s0218001497000081.

Full text

Abstract:

A powerful and universal data structure with applications invarious subfields of science and engineering is graphs. In computer vision and image analysis, graphs are often used for the representation of structured objects. For example, if the problem is to recognize instances of known objects in an image, then often models, or prototypes, of the known objects are represented by means of graphs and stored in a database. The unknown objects in the input image are extracted by means of suitable preprocessing and segmentation algorithms, and represented by graphs that are analogous to the model graphs. Thus, the problem of object recognition is transformed into a graph matching problem. In this paper, it is assumed that there is an input graph that is given on-line, and a number of model, or prototype, graphs that are known a priori. We present a new approach to subgraph isomorphism detection which is based on a compact representation of the model graphs that is computed off-line. Subgraphs that appear multiple times within the same or within different model graphs are represented only once, thus reducing the computational effort to detect them in an input graph. In the extreme case where all model graphs are highly similar, the run time of the new algorithm becomes independent of the number of model graphs. We also describe an extension of this method to error-correcting graph matching. Furthermore, an approach to subgraph isomorphism detection based on decision trees is proposed. A decision tree is generated from the models in an off-line phase. This decision tree can be used for subgraph isomorphism detection. The time needed for decision tree traversal is only polynomial in terms of the number of nodes of the input graph. Moreover, the time complexity of the decision tree traversal is completely independent on the number of model graphs, regardless of their similarity. However, the size of the decision tree is exponential in the number of nodes of the models. To cut down the space complexity of the decision tree, some pruning strategies are discussed.

APA, Harvard, Vancouver, ISO, and other styles

5

Smirnov, Alexander Valeryevich. "NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3." Modeling and Analysis of Information Systems 28, no. 1 (March 24, 2021): 22–37. http://dx.doi.org/10.18255/1818-1015-2021-1-22-37.

Full text

Abstract:

In this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or (k + 1) vertices correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of k linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge. A multiple tree is a connected multiple graph with no cycles. Unlike ordinary trees, the number of edges in a multiple tree is not fixed. The problem of finding the spanning tree can be set for a multiple graph. Complete spanning trees form a special class of spanning trees of a multiple graph. Their peculiarity is that a multiple path joining any two selected vertices exists in the tree if and only if such a path exists in the initial graph. If the multiple graph is weighted, the minimum spanning tree problem and the minimum complete spanning tree problem can be set. Also we can formulate the problems of recognition of the spanning tree and complete spanning tree of the limited weight. The main result of this article is the proof of NPcompleteness of such recognition problems for arbitrary multiple graphs as well as for divisible multiple graphs in the case when multiplicity k ≥ 3. The corresponding optimization problems are NP-hard.

APA, Harvard, Vancouver, ISO, and other styles

6

BHABAK, PUSPAL, and HOVHANNES A. HARUTYUNYAN. "Approximation Algorithm for the Broadcast Time in k-Path Graph." Journal of Interconnection Networks 19, no. 04 (December 2019): 1950006. http://dx.doi.org/10.1142/s0219265919500063.

Full text

Abstract:

Broadcasting is an information dissemination problem in a connected network in which one node, called the originator, must distribute a message to all other nodes by placing a series of calls along the communication lines of the network. In every unit of time, the informed nodes aid the originator in distributing the message. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for certain graphs like trees, unicyclic graphs, tree of cycles, necklace graphs, fully connected trees and tree of cliques. In this paper we study the broadcast problem in k-path graphs. For any originator of the k-path graph we present a (4 – ϵ)-approximation algorithm in the worst case. The algorithm gives a better approximation ratio for some large classes of k-path graphs. Moreover, our algorithm generates the optimal broadcast time for some cases.

APA, Harvard, Vancouver, ISO, and other styles

7

LYONS, RUSSELL. "Identities and Inequalities for Tree Entropy." Combinatorics, Probability and Computing 19, no. 2 (December 15, 2009): 303–13. http://dx.doi.org/10.1017/s0963548309990605.

Full text

Abstract:

The notion of tree entropy was introduced by the author as a normalized limit of the number of spanning trees in finite graphs, but is defined on random infinite rooted graphs. We give some new expressions for tree entropy; one uses Fuglede–Kadison determinants, while another uses effective resistance. We use the latter to prove that tree entropy respects stochastic domination. We also prove that tree entropy is non-negative in the unweighted case, a special case of which establishes Lück's Determinant Conjecture for Cayley-graph Laplacians. We use techniques from the theory of operators affiliated to von Neumann algebras.

APA, Harvard, Vancouver, ISO, and other styles

8

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

9

Maksimov, Anatoliy G., Arsenii D. Zavalishin, Maxim V. Abramov, and Alexander L. Tulupyev. "Adjacency Tree Families and Complementarity Criteria." Computer tools in education, no. 1 (March 30, 2020): 28–37. http://dx.doi.org/10.32603/2071-2340-2020-1-28-37.

Full text

Abstract:

The article is aimed at generalizing the concepts of a derivative graph and a primitive graph for graphs with trunk connectivity. Theorems are formulated and proved on the main connectedness of the graph of the derivative and on the graph of the antiderivative main connected graphs. The theoretical and practical significance lies in the study of structures that will be best suited for working with algebraic Bayesian networks and, thus, become one of the goal of their machine learning. We note the novelty of looking at the problem, or rather, studying the question for which families of graphs there is a set of loads, the family of MGS over which exactly coincides with the given one.

APA, Harvard, Vancouver, ISO, and other styles

10

Smirnov, Alexander V. "The Spanning Tree of a Divisible Multiple Graph." Modeling and Analysis of Information Systems 25, no. 4 (August 27, 2018): 388–401. http://dx.doi.org/10.18255/1818-1015-2018-4-388-401.

Full text

Abstract:

In this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or k + 1 vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges, and it can be the common ending vertex to k linked edges of a multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of any other multi-edge. Special attention is paid to the class of divisible multiple graphs. The main peculiarity of them is a possibility to divide the graph into k parts, which are adjusted on the linked edges and which have no common edges. Each part is an ordinary graph. The definition of a multiple tree is stated and the basic properties of such trees are studied. Unlike ordinary trees, the number of edges in a multiple tree is not fixed. In the article, the evaluation of the minimum and maximum number of edges in the divisible tree is stated and proved. Next, the definitions of the spanning tree and the complete spanning tree of a multiple graph are given. The criterion of completeness of the spanning tree is proved for divisible graphs. It is also proved that a complete spanning tree exists in any divisible graph. If the multiple graph is weighted, the minimum spanning tree problem and the minimum complete spanning tree problem can be set. In the article, we suggest a heuristic algorithm for the minimum complete spanning tree problem for a divisible graph.

APA, Harvard, Vancouver, ISO, and other styles

11

Murugan, A. Nellai, and Shiny Priyanka. "TREE RELATED EXTENDED MEAN CORDIAL GRAPHS." International Journal of Research -GRANTHAALAYAH 3, no. 9 (September 30, 2015): 143–48. http://dx.doi.org/10.29121/granthaalayah.v3.i9.2015.2954.

Full text

Abstract:

Let G = (V,E) be a graph with p vertices and q edges. A Extended Mean Cordial Labeling of a Graph G with vertex set V is a bijection from V to {0, 1,2} such that each edge uv is assigned the label where ⌈ x ⌉ is the least integer greater than or equal to x with the condition that the number of vertices labeled with 0 and the number of vertices labeled with 1 differ by at most 1 and the number of edges labeled with 0 and the number of edges labeled with 1 differ by almost 1. The graph that admits an Extended Mean Cordial Labeling is called Extended Mean Cordial Graph. In this paper, we proved that tree related graphs Hdn, K 1,n, Tgn, <K1,n:n> are Extended Mean Cordial Graphs.

APA, Harvard, Vancouver, ISO, and other styles

12

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

13

Reddy, K. Krishna Mohan, P. Renjith, and N. Sadagopan. "Listing all spanning trees in Halin graphs — sequential and Parallel view." Discrete Mathematics, Algorithms and Applications 10, no. 01 (February 2018): 1850005. http://dx.doi.org/10.1142/s1793830918500052.

Full text

Abstract:

For a connected labeled graph [Formula: see text], a spanning tree [Formula: see text] is a connected and acyclic subgraph that spans all vertices of [Formula: see text]. In this paper, we consider a classical combinatorial problem which is to list all spanning trees of [Formula: see text]. A Halin graph is a graph obtained from a tree with no degree two vertices and by joining all leaves with a cycle. We present a sequential and parallel algorithm to enumerate all spanning trees in Halin graphs. Our approach enumerates without repetitions and we make use of [Formula: see text] processors for parallel algorithmics, where [Formula: see text] and [Formula: see text] are the depth, the number of leaves, respectively, of the Halin graph. We also prove that the number of spanning trees in Halin graphs is [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

14

HIGA, YASUTO, HIDEO BANNAI, SHUNSUKE INENAGA, and MASAYUKI TAKEDA. "REACHABILITY ON SUFFIX TREE GRAPHS." International Journal of Foundations of Computer Science 19, no. 01 (February 2008): 147–62. http://dx.doi.org/10.1142/s0129054108005590.

Full text

Abstract:

We analyze the complexity of graph reachability queries on ST-graphs, defined as directed acyclic graphs (DAGs) obtained by merging the suffix tree of a given string and its suffix links. Using a simplified reachability labeling algorithm presented by Agrawal et al. (1989), we show that for a random string of length n, its ST-graph can be preprocessed in O(n log n) expected time and space to answer reachability queries in O( log n) time. Furthermore, we present a series of strings that require [Formula: see text] time and space to answer reachability queries in O( log n) time for the same algorithm. Exhaustive computational calculations for strings of length n ≤ 33 have revealed that the same strings are also the worst case instances of the algorithm. We therefore conjecture that reachability queries can be answered in O( log n) time with a worst case time and space preprocessing complexity of [Formula: see text].

APA, Harvard, Vancouver, ISO, and other styles

15

Alcón, Liliana, Celina H. de Figueiredo, Marcia Cerioli, Marisa Gutierrez, and João Meidanis. "Tree Loop Graphs." Electronic Notes in Discrete Mathematics 18 (December 2004): 17–23. http://dx.doi.org/10.1016/j.endm.2004.06.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Alcón, Liliana, Márcia R. Cerioli, Celina M. H. de Figueiredo, Marisa Gutierrez, and João Meidanis. "Tree loop graphs." Discrete Applied Mathematics 155, no. 6-7 (April 2007): 686–94. http://dx.doi.org/10.1016/j.dam.2005.01.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Liu, Jia-Bao, and Salama Nagy Daoud. "The Complexity of Some Classes of Pyramid Graphs Created from a Gear Graph." Symmetry 10, no. 12 (December 2, 2018): 689. http://dx.doi.org/10.3390/sym10120689.

Full text

Abstract:

The methods of measuring the complexity (spanning trees) in a finite graph, a problem related to various areas of mathematics and physics, have been inspected by many mathematicians and physicists. In this work, we defined some classes of pyramid graphs created by a gear graph then we developed the Kirchhoff's matrix tree theorem method to produce explicit formulas for the complexity of these graphs, using linear algebra, matrix analysis techniques, and employing knowledge of Chebyshev polynomials. Finally, we gave some numerical results for the number of spanning trees of the studied graphs.

APA, Harvard, Vancouver, ISO, and other styles

18

Zhong, Lei, and Wen-Huan Wang. "The signless Laplacian coefficients and the incidence energy of graphs with a given bipartition." Filomat 34, no. 12 (2020): 4215–32. http://dx.doi.org/10.2298/fil2012215z.

Full text

Abstract:

We consider two classes of the graphs with a given bipartition. One is trees and the other is unicyclic graphs. The signless Laplacian coefficients and the incidence energy are investigated for the sets of trees/unicyclic graphs with n vertices in which each tree/unicyclic graph has an (n1,n2)-bipartition, where n1 and n2 are positive integers not less than 2 and n1+n2 = n. Four new graph transformations are proposed for studying the signless Laplacian coefficients. Among the sets of trees/unicyclic graphs considered, we obtain exactly, for each, the minimal element with respect to the quasi-ordering according to their signless Laplacian coefficients and the element with the minimal incidence energies.

APA, Harvard, Vancouver, ISO, and other styles

19

Sufia Aziz. "Characteristic Graph vs Benzenoid Graph." Mathematical Journal of Interdisciplinary Sciences 7, no. 2 (March 6, 2019): 135–47. http://dx.doi.org/10.15415/mjis.2019.72018.

Full text

Abstract:

A characteristic graph is a tree representative of its corresponding benzenoid (cyclic) graph. It may contain necessary information of several properties of benzenoids. The PI-index of benzenoids and their characteristic graphs are compared by correlating it to a structural property (π-electron energy) of the benzenoids using MLR analysis. PI index being applicable to both trees and cyclic graphs, yielded required results for benzenoid and their characteristic graph.

APA, Harvard, Vancouver, ISO, and other styles

20

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

21

YANHAONA, MUHAMMAD NUR, MD SHAMSUZZOHA BAYZID, and MD SAIDUR RAHMAN. "DISCOVERING PAIRWISE COMPATIBILITY GRAPHS." Discrete Mathematics, Algorithms and Applications 02, no. 04 (December 2010): 607–23. http://dx.doi.org/10.1142/s1793830910000917.

Full text

Abstract:

Let T be an edge weighted tree, let dT(u, v) be the sum of the weights of the edges on the path from u to v in T, and let d min and d max be two non-negative real numbers such that d min ≤ d max . Then a pairwise compatibility graph of T for d min and d max is a graph G = (V, E), where each vertex u' ∈ V corresponds to a leaf u of T and there is an edge (u', v') ∈ E if and only if d min ≤ dT(u, v) ≤ d max . A graph G is called a pairwise compatibility graph (PCG) if there exists an edge weighted tree T and two non-negative real numbers d min and d max such that G is a pairwise compatibility graph of T for d min and d max . Kearney et al. conjectured that every graph is a PCG [3]. In this paper, we refute the conjecture by showing that not all graphs are PCG s . Moreover, we recognize several classes of graphs as pairwise compatibility graphs. We identify two restricted classes of bipartite graphs as PCG. We also show that the well known tree power graphs and some of their extensions are PCGs.

APA, Harvard, Vancouver, ISO, and other styles

22

Xu, Kexiang, Hongshuang Liu, and Kinkar Ch Das. "The Kirchhoff Index of Quasi-Tree Graphs." Zeitschrift für Naturforschung A 70, no. 3 (March 1, 2015): 135–39. http://dx.doi.org/10.1515/zna-2014-0230.

Full text

Abstract:

AbstractResistance distance was introduced by Klein and Randić as a generalisation of the classical distance. The Kirchhoff index Kf(G) of a graph G is the sum of resistance distances between all unordered pairs of vertices. In this article we characterise the extremal graphs with the maximal Kirchhoff index among all non-trivial quasi-tree graphs of order n. Moreover, we obtain a lower bound on the Kirchhoff index for all non-trivial quasi-tree graphs of order n.

APA, Harvard, Vancouver, ISO, and other styles

23

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

24

Schaller, David, Manuela Geiß, Marc Hellmuth, and Peter F. Stadler. "Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs." Algorithms 14, no. 4 (March 29, 2021): 110. http://dx.doi.org/10.3390/a14040110.

Full text

Abstract:

Best match graphs (BMGs) are vertex-colored digraphs that naturally arise in mathematical phylogenetics to formalize the notion of evolutionary closest genes w.r.t. an a priori unknown phylogenetic tree. BMGs are explained by unique least resolved trees. We prove that the property of a rooted, leaf-colored tree to be least resolved for some BMG is preserved by the contraction of inner edges. For the special case of two-colored BMGs, this leads to a characterization of the least resolved trees (LRTs) of binary-explainable trees and a simple, polynomial-time algorithm for the minimum cardinality completion of the arc set of a BMG to reach a BMG that can be explained by a binary tree.

APA, Harvard, Vancouver, ISO, and other styles

25

Diestel, Reinhard. "Simplicial minors and decompositions of graphs." Mathematical Proceedings of the Cambridge Philosophical Society 103, no. 3 (May 1988): 409–26. http://dx.doi.org/10.1017/s0305004100065026.

Full text

Abstract:

The purpose of this paper is to give natural characterizations of the countable graphs that admit tree-decompositions or simplicial tree-decompositions into primes. Tree-decompositions were recently introduced by Robertson and Seymour in their series of papers on graph minors [7]. Simplicial tree-decompositions were first considered by Halin[6], being the most typical kind of ‘simplicial decomposition’ as introduced by Halin[5] in 1964. The problem of determining which infinite graphs admit a simplicial decomposition into primes has stood unresolved since then; a first solution for simplicial tree-decompositions was given in [2].

APA, Harvard, Vancouver, ISO, and other styles

26

Band, Ram. "The nodal count {0,1,2,3,…} implies the graph is a tree." Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 372, no. 2007 (January 28, 2014): 20120504. http://dx.doi.org/10.1098/rsta.2012.0504.

Full text

Abstract:

Sturm's oscillation theorem states that the n th eigenfunction of a Sturm–Liouville operator on the interval has n −1 zeros (nodes) (Sturm 1836 J. Math. Pures Appl. 1 , 106–186; 373–444). This result was generalized for all metric tree graphs (Pokornyĭ et al. 1996 Mat. Zametki 60 , 468–470 ( doi:10.1007/BF02320380 ); Schapotschnikow 2006 Waves Random Complex Media 16 , 167–178 ( doi:10.1080/1745530600702535 )) and an analogous theorem was proved for discrete tree graphs (Berkolaiko 2007 Commun. Math. Phys. 278 , 803–819 ( doi:10.1007/S00220-007-0391-3 ); Dhar & Ramaswamy 1985 Phys. Rev. Lett. 54 , 1346–1349 ( doi:10.1103/PhysRevLett.54.1346 ); Fiedler 1975 Czechoslovak Math. J. 25 , 607–618). We prove the converse theorems for both discrete and metric graphs. Namely if for all n , the n th eigenfunction of the graph has n −1 zeros, then the graph is a tree. Our proofs use a recently obtained connection between the graph's nodal count and the magnetic stability of its eigenvalues (Berkolaiko 2013 Anal. PDE 6 , 1213–1233 ( doi:10.2140/apde.2013.6.1213 ); Berkolaiko & Weyand 2014 Phil. Trans. R. Soc. A 372 , 20120522 ( doi:10.1098/rsta.2012.0522 ); Colin de Verdière 2013 Anal. PDE 6 , 1235–1242 ( doi:10.2140/apde.2013.6.1235 )). In the course of the proof, we show that it is not possible for all (or even almost all, in the metric case) the eigenvalues to exhibit a diamagnetic behaviour. In addition, we develop a notion of ‘discretized’ versions of a metric graph and prove that their nodal counts are related to those of the metric graph.

APA, Harvard, Vancouver, ISO, and other styles

27

FOX, JACOB, and JÁNOS PACH. "A Separator Theorem for String Graphs and its Applications." Combinatorics, Probability and Computing 19, no. 3 (October 7, 2009): 371–90. http://dx.doi.org/10.1017/s0963548309990459.

Full text

Abstract:

A string graph is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with m edges can be separated into two parts of roughly equal size by the removal of $O(m^{3/4}\sqrt{\log m})$ vertices. This result is then used to deduce that every string graph with n vertices and no complete bipartite subgraph Kt,t has at most ctn edges, where ct is a constant depending only on t. Another application shows that locally tree-like string graphs are globally tree-like: for any ε > 0, there is an integer g(ε) such that every string graph with n vertices and girth at least g(ε) has at most (1 + ε)n edges. Furthermore, the number of such labelled graphs is at most (1 + ε)nT(n), where T(n) = nn−2 is the number of labelled trees on n vertices.

APA, Harvard, Vancouver, ISO, and other styles

28

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

29

Xu, Zhao Di, Xiao Yi Li, and Wan Xi Chou. "Methods of Constructing and Enumerating the Spanning Tree of a Connected Graph." Applied Mechanics and Materials 496-500 (January 2014): 2363–66. http://dx.doi.org/10.4028/www.scientific.net/amm.496-500.2363.

Full text

Abstract:

A definition concerning the spanning sub graph and spanning sub graph circle is given. Use the enumerating methods of spanning sub circle; seek out the spanning sub graph of spanning trees. The theorems of constructing and enumerating the spanning trees are proved. The methods of enumerating and constructing connected graph spanning tree are proposed. The application examples of construction theorem and enumerating theorem are given. the spanning sub graphs number of five plane graph and the construction of Constituent sub-graph are introduced, thus verifying constructing and enumerating theorem are useful and effective. This method Is a Simple and easy method to construct the spanning tree of connected graph.

APA, Harvard, Vancouver, ISO, and other styles

30

Brown, David E., and Breeann M. Flesch. "A Characterization of 2-Tree Proper Interval 3-Graphs." Journal of Discrete Mathematics 2014 (February 23, 2014): 1–7. http://dx.doi.org/10.1155/2014/143809.

Full text

Abstract:

An interval p-graph is the intersection graph of a collection of intervals which have been colored with p different colors with edges corresponding to nonempty intersection of intervals from different color classes. We characterize the class of 2-trees which are interval 3-graphs via a list of three graphs and three infinite families of forbidden induced subgraphs.

APA, Harvard, Vancouver, ISO, and other styles

31

Kwun, Young Chel, Hafiz Mutee ur Rehman, Muhammad Yousaf, Waqas Nazeer, and Shin Min Kang. "The Entropy of Weighted Graphs with Atomic Bond Connectivity Edge Weights." Discrete Dynamics in Nature and Society 2018 (December 16, 2018): 1–10. http://dx.doi.org/10.1155/2018/8407032.

Full text

Abstract:

The aim of this report to solve the open problem suggested by Chen et al. We study the graph entropy with ABC edge weights and present bounds of it for connected graphs, regular graphs, complete bipartite graphs, chemical graphs, tree, unicyclic graphs, and star graphs. Moreover, we compute the graph entropy for some families of dendrimers.

APA, Harvard, Vancouver, ISO, and other styles

32

Messmer, B. T., and H. Bunke. "Error-Correcting Graph Isomorphism Using Decision Trees." International Journal of Pattern Recognition and Artificial Intelligence 12, no. 06 (September 1998): 721–42. http://dx.doi.org/10.1142/s0218001498000415.

Full text

Abstract:

In this paper we present a fast algorithm for the computation of error-correcting graph isomorphisms. The new algorithm is an extension of a method for exact subgraph isomorphism detection from an input graph to a set of a priori known model graphs, which was previously developed by the authors. Similar to the original algorithm, the new method is based on the idea of creating a decision tree from the model graphs. This decision tree is compiled off-line in a preprocessing step. At run time, it is used to find all error-correcting graph isomorphisms from an input graph to any of the model graphs up to a certain degree of distortion. The main advantage of the new algorithm is that error-correcting graph isomorphism detection is guaranteed to require time that is only polynomial in terms of the size of the input graph. Furthermore, the time complexity is completely independent of the number of model graphs and the number of edges in each model graph. However, the size of the decision tree is exponential in the size of the model graphs and the degree of error. Nevertheless, practical experiments have indicated that the method can be applied to graphs containing up to 16 vertices.

APA, Harvard, Vancouver, ISO, and other styles

33

Jahari, Somayeh, and Saeid Alikhani. "Domination Polynomials of k-Tree Related Graphs." International Journal of Combinatorics 2014 (November 11, 2014): 1–5. http://dx.doi.org/10.1155/2014/390170.

Full text

Abstract:

Let G be a simple graph of order n. The domination polynomial of G is the polynomial DG,x=∑i=γ(G)nd(G,i)xi, where d(G, i) is the number of dominating sets of G of size i and γ(G) is the domination number of G. In this paper, we study the domination polynomials of several classes of k-tree related graphs. Also, we present families of these kinds of graphs, whose domination polynomials have no nonzero real roots.

APA, Harvard, Vancouver, ISO, and other styles

34

Cohen, Joel E. "Connectivity of finite anisotropic random graphs and directed graphs." Mathematical Proceedings of the Cambridge Philosophical Society 99, no. 2 (March 1986): 315–30. http://dx.doi.org/10.1017/s0305004100064239.

Full text

Abstract:

AbstractFor graphs on a finite set of vertices with arbitrary probabilities of independently occurring edges, the reliability is defined as the probability that the graph is connected, and the redundancy as the expected number of spanning trees of the graph. Analogous measures of connectivity are defined for random finite directed graphs with arbitrary probabilities of independently occurring directed edges. Recursive formulas for computing the reliability are known. Determinantal formulas, based on matrix-tree theorems, for computing the redundancy are given here. Among random graphs with a given sum of edge probabilities, the more evenly the probabilities are distributed over potential edges, the larger the redundancy. This inequality, proved using the theory of majorization, in combination with examples shows unexpectedly that conflicts between reliability and redundancy can arise in the design of communication networks modelled by such random graphs. The significance of these calculations for the command and control of nuclear forces is sketched.

APA, Harvard, Vancouver, ISO, and other styles

35

Shiono, Yasunori, Tadaaki Kirishima, Yoshinori Ueda, and Kensei Tsuchida. "Drawing Algorithm for Fuzzy Graphs Using the Partition Tree." Journal of Advanced Computational Intelligence and Intelligent Informatics 16, no. 5 (July 20, 2012): 641–52. http://dx.doi.org/10.20965/jaciii.2012.p0641.

Full text

Abstract:

Fuzzy graphs have been used frequently and effectively as a method for sociogram analysis. A fuzzy graph has the fundamental characteristic of being able to express a variety of relationships between nodes. The drawing of fuzzy graphs has been studied in computer-aided analysis systems with human interfaces and methods using genetic algorithms. However, computer-aided analysis systems with human interfaces do not provide for automatic drawing, while methods using genetic algorithms have the defect of requiring too much execution time for finding a locally optimum solution. To overcome these defects, we propose an algorithm for drawing intelligible and comprehensive fuzzy graphs using a partition tree. This method automatically draws the fuzzy graphwith nodes arranged on the intersections of a latticed space. Since nodes are optimally arranged on the latticed intersections and put together at a nearby position in accordance with the transition of clusters according to cluster levels in the partition tree, drawing the algorithm makes fuzzy relations easier to understand through fuzzy graph representation. Moreover, fuzzy graphs can be drawn faster than by conventional methods. This paper describes the algorithm and its verification by introducing a system implementing the method for displaying fuzzy graphs. Moreover, we have carried out a case study in which a questionnaire has been administered to students, allowing us to analyze human relations quantitatively using a method based on fuzzy theory. Human relations are represented as fuzzy graphs by our algorithm and analyzed using the fuzzy graph.

APA, Harvard, Vancouver, ISO, and other styles

36

V J Kaneria, H P Chudasama, and P P Andharia. "Absolute Mean Graceful Labeling in Path Union of Various Graphs." Mathematical Journal of Interdisciplinary Sciences 7, no. 1 (September 6, 2018): 51–56. http://dx.doi.org/10.15415/mjis.2018.71008.

Full text

Abstract:

Present paper aims to focus on absolute mean graceful labeling in path union of various graphs. We proved path union of graphs like tree, path Pn, cycle Cn, complete bipartite graph Km, n, grid graph PM × Pn, step grid graph Stn and double step grid graph DStn are absolute mean graceful graphs.

APA, Harvard, Vancouver, ISO, and other styles

37

Yuster, Raphael. "Tree decomposition of graphs." Random Structures and Algorithms 12, no. 3 (May 1998): 237–51. http://dx.doi.org/10.1002/(sici)1098-2418(199805)12:3<237::aid-rsa2>3.0.co;2-w.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Artes, Jr., Rosalio G., and Rene D. Dignos. "Tree cover of graphs." Applied Mathematical Sciences 8 (2014): 7469–73. http://dx.doi.org/10.12988/ams.2014.49728.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Eaton, Nancy, Zoltán Füredi, Alexandr V. Kostochka, and Jozef Skokan. "Tree representations of graphs." European Journal of Combinatorics 28, no. 4 (May 2007): 1087–98. http://dx.doi.org/10.1016/j.ejc.2006.04.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Berman, Leah Wrenn, Glenn G. Chappell, Jill R. Faudree, John Gimbel, and Chris Hartman. "Uniquely Tree-saturated Graphs." Graphs and Combinatorics 32, no. 2 (June 5, 2015): 463–94. http://dx.doi.org/10.1007/s00373-015-1589-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Diestel, Reinhard. "Tree-decompositions, tree-representability and chordal graphs." Discrete Mathematics 71, no. 2 (1988): 181–84. http://dx.doi.org/10.1016/0012-365x(88)90071-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Zhu, Enqiang, Zepeng Li, Zehui Shao, Jin Xu, and Chanjuan Liu. "Tree-core and tree-coritivity of graphs." Information Processing Letters 115, no. 10 (October 2015): 754–59. http://dx.doi.org/10.1016/j.ipl.2015.02.016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

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

44

Biane, Philippe, and Guillaume Chapuy. "Laplacian matrices and spanning trees of tree graphs." Annales de la faculté des sciences de Toulouse Mathématiques 26, no. 2 (2017): 235–61. http://dx.doi.org/10.5802/afst.1532.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

S, Sunoj B., and Mathew Varkey T. K. "Oblong Mean Prime Labeling of Some Tree Graphs." International Journal of Trend in Scientific Research and Development Volume-2, Issue-2 (February 28, 2018): 222–26. http://dx.doi.org/10.31142/ijtsrd8375.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

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

47

Wu, Tingzeng, and Huazhong Lü. "The Extremal Permanental Sum for a Quasi-Tree Graph." Complexity 2019 (May 20, 2019): 1–4. http://dx.doi.org/10.1155/2019/4387650.

Full text

Abstract:

Let G be a graph and A(G) the adjacency matrix of G. The permanent of matrix (xI-A(G)) is called the permanental polynomial of G. The permanental sum of G is the sum of the absolute values of the coefficients of permanental polynomial of G. Computing the permanental sum is #p-complete. In this note, we prove the maximum value and the minimum value of permanental sum of quasi-tree graphs. And the corresponding extremal graphs are also determined. Furthermore,we also determine the graphs with the minimum permanental sum among quasi-tree graphs of order n and size m, where n-1≤m≤2n-3.

APA, Harvard, Vancouver, ISO, and other styles

48

SUN, YUEFANG. "The (3, l)-Rainbow Edge-Index of Cartesian Product Graphs." Journal of Interconnection Networks 17, no. 03n04 (September 2017): 1741009. http://dx.doi.org/10.1142/s0219265917410092.

Full text

Abstract:

For a graph G and a vertex subset [Formula: see text] of at least two vertices, an S-tree is a subgraph T of G that is a tree with [Formula: see text]. Two S-trees are said to be edge-disjoint if they have no common edge. Let [Formula: see text] denote the maximum number of edge-disjoint S-trees in G. For an integer K with [Formula: see text], the generalized k-edge-connectivity is defined as [Formula: see text]. An S-tree in an edge-colored graph is rainbow if no two edges of it are assigned the same color. Let [Formula: see text] and l be integers with [Formula: see text], the [Formula: see text]-rainbow edge-index [Formula: see text] of G is the smallest number of colors needed in an edge-coloring of G such that for every set S of k vertices of G, there exist l edge-disjoint rainbow S-trees.In this paper, we study the [Formula: see text]-rainbow edge-index of Cartesian product graphs and get a sharp upper bound for [Formula: see text] , where G and H are connected graphs with orders at least three, and [Formula: see text] denotes the Cartesian product of G and H.

APA, Harvard, Vancouver, ISO, and other styles

49

Kozerenko, Sergiy. "More on linear and metric tree maps." Opuscula Mathematica 41, no. 1 (2021): 55–70. http://dx.doi.org/10.7494/opmath.2021.41.1.55.

Full text

Abstract:

We consider linear and metric self-maps on vertex sets of finite combinatorial trees. Linear maps are maps which preserve intervals between pairs of vertices whereas metric maps are maps which do not increase distances between pairs of vertices. We obtain criteria for a given linear or a metric map to be a positive (negative) under some orientation of the edges in a tree, we characterize trees which admit maps with Markov graphs being paths and prove that the converse of any partial functional digraph is isomorphic to a Markov graph for some suitable map on a tree.

APA, Harvard, Vancouver, ISO, and other styles

50

LIN, LAN, and YIXUN LIN. "The Minimum Stretch Spanning Tree Problem for Hamming Graphs and Higher-Dimensional Grids." Journal of Interconnection Networks 20, no. 01 (March 2020): 2050004. http://dx.doi.org/10.1142/s0219265920500048.

Full text

Abstract:

The minimum stretch spanning tree problem for a graph G is to find a spanning tree T of G such that the maximum distance in T between two adjacent vertices is minimized. The minimum value of this optimization problem gives rise to a graph invariant σ(G), called the tree-stretch of G. The problem has been proved NP-hard. In this paper we present a general approach to determine the exact values σ(G) for a series of typical graphs arising from communication networks, such as Hamming graphs and higher-dimensional grids (including hypercubes).

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!