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 107 Next

Displaying 2121 – 2140 of 5365

Showing per page

Highly connected counterexamples to a conjecture on α-domination

Zsolt Tuza (2005)

Discussiones Mathematicae Graph Theory

An infinite class of counterexamples is given to a conjecture of Dahme et al. [1] concerning the minimum size of a dominating vertex set that contains at least a prescribed proportion of the neighbors of each vertex not belonging to the set.

Histories in path graphs

Ludovít Niepel (2007)

Discussiones Mathematicae Graph Theory

For a given graph G and a positive integer r the r-path graph, P r ( G ) , has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let P r k ( G ) be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of P r k ( G ) . The k-history P r - k ( H ) is a subgraph of G that is induced by all edges that take part in the recursive definition of...

(H,k) stable bipartite graphs with minimum size

Aneta Dudek, Małgorzata Zwonek (2009)

Discussiones Mathematicae Graph Theory

Let us call a graph G(H;k) vertex stable if it contains a subgraph H after removing any of its k vertices. In this paper we are interested in finding the ( K n , n + 1 ; 1 ) (respectively ( K n , n ; 1 ) ) vertex stable graphs with minimum size.

(H,k) stable graphs with minimum size

Aneta Dudek, Artur Szymański, Małgorzata Zwonek (2008)

Discussiones Mathematicae Graph Theory

Let us call a G (H,k) graph vertex stable if it contains a subgraph H ever after removing any of its k vertices. By Q(H,k) we will denote the minimum size of an (H,k) vertex stable graph. In this paper, we are interested in finding Q(₃,k), Q(₄,k), Q ( K 1 , p , k ) and Q(Kₛ,k).

Holes in graphs.

Peng, Yuejian, Rödl, Vojtech, Ruciński, Andrzej (2002)

The Electronic Journal of Combinatorics [electronic only]

Homogeneous colourings of graphs

Tomáš Madaras, Mária Šurimová (2023)

Mathematica Bohemica

A proper vertex k -colouring of a graph G is called l -homogeneous if the number of colours in the neigbourhood of each vertex of G equals l . We explore basic properties (the existence and the number of used colours) of homogeneous colourings of graphs in general as well as of some specific graph families, in particular planar graphs.

Homogeneously embedding stratified graphs in stratified graphs

Gary Chartrand, Donald W. Vanderjagt, Ping Zhang (2005)

Mathematica Bohemica

A 2-stratified graph G is a graph whose vertex set has been partitioned into two subsets, called the strata or color classes of G . Two 2 -stratified graphs G and H are isomorphic if there exists a color-preserving isomorphism φ from G to H . A 2 -stratified graph G is said to be homogeneously embedded in a 2 -stratified graph H if for every vertex x of G and every vertex y of H , where x and y are colored the same, there exists an induced 2 -stratified subgraph H ' of H containing y and a color-preserving...

Homomorphism duality for rooted oriented paths

Petra Smolíková (2000)

Commentationes Mathematicae Universitatis Carolinae

Let ( H , r ) be a fixed rooted digraph. The ( H , r ) -coloring problem is the problem of deciding for which rooted digraphs ( G , s ) there is a homomorphism f : G → H which maps the vertex s to the vertex r . Let ( H , r ) be a rooted oriented path. In this case we characterize the nonexistence of such a homomorphism by the existence of a rooted oriented cycle ( C , q ) , which is homomorphic to ( G , s ) but not homomorphic to ( H , r ) . Such a property of the digraph ( H , r ) is called rooted cycle duality or * -cycle duality. This extends the analogical result for...

Currently displaying 2121 – 2140 of 5365