All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 5 Next

Displaying 81 – 100 of 321

Showing per page

Distance coloring of the hexagonal lattice

Peter Jacko, Stanislav Jendrol' (2005)

Discussiones Mathematicae Graph Theory

Motivated by the frequency assignment problem we study the d-distant coloring of the vertices of an infinite plane hexagonal lattice H. Let d be a positive integer. A d-distant coloring of the lattice H is a coloring of the vertices of H such that each pair of vertices distance at most d apart have different colors. The d-distant chromatic number of H, denoted χ d ( H ) , is the minimum number of colors needed for a d-distant coloring of H. We give the exact value of χ d ( H ) for any d odd and estimations for any...

Distance defined by spanning trees in graphs

Gary Chartrand, Ladislav Nebeský, Ping Zhang (2007)

Discussiones Mathematicae Graph Theory

For a spanning tree T in a nontrivial connected graph G and for vertices u and v in G, there exists a unique u-v path u = u₀, u₁, u₂,..., uₖ = v in T. A u-v T-path in G is a u- v path u = v₀, v₁,...,vₗ = v in G that is a subsequence of the sequence u = u₀, u₁, u₂,..., uₖ = v. A u-v T-path of minimum length is a u-v T-geodesic in G. The T-distance d G | T ( u , v ) from u to v in G is the length of a u-v T-geodesic. Let geo(G) and geo(G|T) be the set of geodesics and the set of T-geodesics respectively in G. Necessary...

Distance in stratified graphs

Gary Chartrand, Lisa Hansen, Reza Rashidi, Naveed Sherwani (2000)

Czechoslovak Mathematical Journal

A graph G is stratified if its vertex set is partitioned into classes, called strata. If there are k strata, then G is k -stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color X in a stratified graph G , the X -eccentricity e X ( v ) of a vertex v of G is the distance between v and an X -colored vertex furthest from v . The minimum X -eccentricity among the vertices of G is the X -radius r a d X G of G and the maximum...

Distance independence in graphs

J. Louis Sewell, Peter J. Slater (2011)

Discussiones Mathematicae Graph Theory

For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u,v) ∉ D. The D-independence number β D ( G ) is the maximum cardinality of a D-independent set. In particular, the independence number β ( G ) = β 1 ( G ) . Along with general results we consider, in particular, the odd-independence number β O D D ( G ) where ODD = 1,3,5,....

Distance-Locally Disconnected Graphs

Mirka Miller, Joe Ryan, Zdeněk Ryjáček (2013)

Discussiones Mathematicae Graph Theory

For an integer k ≥ 1, we say that a (finite simple undirected) graph G is k-distance-locally disconnected, or simply k-locally disconnected if, for any x ∈ V (G), the set of vertices at distance at least 1 and at most k from x induces in G a disconnected graph. In this paper we study the asymptotic behavior of the number of edges of a k-locally disconnected graph on n vertices. For general graphs, we show that this number is Θ(n2) for any fixed value of k and, in the special case of regular graphs,...

Distances between rooted trees

Bohdan Zelinka (1991)

Mathematica Bohemica

Two types of a distance between isomorphism classes of graphs are adapted for rooted trees.

Double geodetic number of a graph

A.P. Santhakumaran, T. Jebaraj (2012)

Discussiones Mathematicae Graph Theory

For a connected graph G of order n, a set S of vertices is called a double geodetic set of G if for each pair of vertices x,y in G there exist vertices u,v ∈ S such that x,y ∈ I[u,v]. The double geodetic number dg(G) is the minimum cardinality of a double geodetic set. Any double godetic of cardinality dg(G) is called dg-set of G. The double geodetic numbers of certain standard graphs are obtained. It is shown that for positive integers r,d such that r < d ≤ 2r and 3 ≤ a ≤ b there exists a connected...

Edge shift distance between trees

Bohdan Zelinka (1992)

Archivum Mathematicum

Edge shift distance between isomorphism classes of graphs, introduced by M. Johnson, is investigated in the case of trees and compared with other distances.

Edit distance between unlabeled ordered trees

Anne Micheli, Dominique Rossin (2006)

RAIRO - Theoretical Informatics and Applications

There exists a bijection between one-stack sortable permutations (permutations which avoid the pattern (231)) and rooted plane trees. We define an edit distance between permutations which is consistent with the standard edit distance between trees. This one-to-one correspondence yields a polynomial algorithm for the subpermutation problem for (231) pattern-avoiding permutations. Moreover, we obtain the generating function of the edit distance between ordered unlabeled trees and some special ones. For...

Currently displaying 81 – 100 of 321