Displaying similar documents to “Enumeration of spanning trees in the sequence of Dürer graphs”

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....

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...

Structural results on maximal k-degenerate graphs

Allan Bickle (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is k-degenerate if its vertices can be successively deleted so that when deleted, each has degree at most k. These graphs were introduced by Lick and White in 1970 and have been studied in several subsequent papers. We present sharp bounds on the diameter of maximal k-degenerate graphs and characterize the extremal graphs for the upper bound. We present a simple characterization of the degree sequences of these graphs and consider related results. Considering edge coloring, we...

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...

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...

On θ-graphs of partial cubes

Sandi Klavžar, Matjaz Kovse (2007)

Discussiones Mathematicae Graph Theory

Similarity:

The Θ-graph Θ(G) of a partial cube G is the intersection graph of the equivalence classes of the Djoković-Winkler relation. Θ-graphs that are 2-connected, trees, or complete graphs are characterized. In particular, Θ(G) is complete if and only if G can be obtained from K₁ by a sequence of (newly introduced) dense expansions. Θ-graphs are also compared with familiar concepts of crossing graphs and τ-graphs.

Some globally determined classes of graphs

Ivica Bošnjak, Rozália Madarász (2018)

Czechoslovak Mathematical Journal

Similarity:

For a class of graphs we say that it is globally determined if any two nonisomorphic graphs from that class have nonisomorphic globals. We will prove that the class of so called CCB graphs and the class of finite forests are globally determined.