Displaying similar documents to “Linear and metric maps on trees via Markov graphs”

Enumeration of spanning trees in the sequence of Dürer graphs

Shixing Li (2017)

Open Mathematics

Similarity:

In this paper, we calculate the number of spanning trees in the sequence of Dürer graphs with a special feature that it has two alternate states. Using the electrically equivalent transformations, we obtain the weights of corresponding equivalent graphs and further derive relationships for spanning trees between the Dürer graphs and transformed graphs. By algebraic calculations, we obtain a closed-form formula for the number of spanning trees with regard to iteration step. Finally we...

Gamma Graphs Of Some Special Classes Of Trees

Anna Bień (2015)

Annales Mathematicae Silesianae

Similarity:

A set S ⊂ V is a dominating set of a graph G = (V, E) if every vertex υ ∈ V which does not belong to S has a neighbour in S. The domination number γ(G) of the graph G is the minimum cardinality of a dominating set in G. A dominating set S is a γ-set in G if |S| = γ(G). Some graphs have exponentially many γ-sets, hence it is worth to ask a question if a γ-set can be obtained by some transformations from another γ-set. The study of gamma graphs is an answer to this reconfiguration problem....

Skein algebras of the solid torus and symmetric spatial graphs

Nafaa Chbili (2006)

Fundamenta Mathematicae

Similarity:

We use the topological invariant of spatial graphs introduced by S. Yamada to find necessary conditions for a spatial graph to be periodic with a prime period. The proof of the main result is based on computing the Yamada skein algebra of the solid torus and then proving that it injects into the Kauffman bracket skein algebra of the solid torus.

Two new classes of trees embeddable into hypercubes

Mounira Nekri, Abdelhafid Berrachedi (2010)

RAIRO - Operations Research

Similarity:

The problem of embedding graphs into other graphs is much studied in the graph theory. In fact, much effort has been devoted to determining the conditions under which a graph G is a subgraph of a graph H, having a particular structure. An important class to study is the set of graphs which are embeddable into a hypercube. This importance results from the remarkable properties of the hypercube and its use in several domains, such as: the coding theory, transfer of information, multicriteria...

Line graphs: their maximum nullities and zero forcing numbers

Shaun Fallat, Abolghasem Soltani (2016)

Czechoslovak Mathematical Journal

Similarity:

The maximum nullity over a collection of matrices associated with a graph has been attracting the attention of numerous researchers for at least three decades. Along these lines various zero forcing parameters have been devised and utilized for bounding the maximum nullity. The maximum nullity and zero forcing number, and their positive counterparts, for general families of line graphs associated with graphs possessing a variety of specific properties are analysed. Building upon earlier...

Tree-like isometric subgraphs of hypercubes

Bostjan Brešar, Wilfried Imrich, Sandi Klavžar (2003)

Discussiones Mathematicae Graph Theory

Similarity:

Tree-like isometric subgraphs of hypercubes, or tree-like partial cubes as we shall call them, are a generalization of median graphs. Just as median graphs they capture numerous properties of trees, but may contain larger classes of graphs that may be easier to recognize than the class of median graphs. We investigate the structure of tree-like partial cubes, characterize them, and provide examples of similarities with trees and median graphs. For instance, we show that the cube graph...

Statuses and double branch weights of quadrangular outerplanar graphs

Halina Bielak, Kamil Powroźnik (2015)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

In this paper we study some distance properties of outerplanar graphs with the Hamiltonian cycle whose all bounded faces are cycles isomorphic to the cycle C4. We call this family of graphs quadrangular outerplanar graphs. We give the lower and upper bound on the double branch weight and the status for this graphs. At the end of this paper we show some relations between median and double centroid in quadrangular outerplanar graphs.

Statuses and double branch weights of quadrangular outerplanar graphs

Halina Bielak, Kamil Powroźnik (2015)

Annales UMCS, Mathematica

Similarity:

In this paper we study some distance properties of outerplanar graphs with the Hamiltonian cycle whose all bounded faces are cycles isomorphic to the cycle C4. We call this family of graphs quadrangular outerplanar graphs. We give the lower and upper bound on the double branch weight and the status for this graphs. At the end of this paper we show some relations between median and double centroid in quadrangular outerplanar graphs

The inertia of unicyclic graphs and bicyclic graphs

Ying Liu (2013)

Discussiones Mathematicae - General Algebra and Applications

Similarity:

Let G be a graph with n vertices and ν(G) be the matching number of G. The inertia of a graph G, In(G) = (n₊,n₋,n₀) is an integer triple specifying the numbers of positive, negative and zero eigenvalues of the adjacency matrix A(G), respectively. Let η(G) = n₀ denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G) = n - 2ν(G). Guo et al. [Ji-Ming Guo, Weigen Yan and Yeong-Nan Yeh. On the nullity and the matching number...