Page 1 Next

Displaying 1 – 20 of 82

Showing per page

On 1-dependent ramsey numbers for graphs

E.J. Cockayne, C.M. Mynhardt (1999)

Discussiones Mathematicae Graph Theory

A set X of vertices of a graph G is said to be 1-dependent if the subgraph of G induced by X has maximum degree one. The 1-dependent Ramsey number t₁(l,m) is the smallest integer n such that for any 2-edge colouring (R,B) of Kₙ, the spanning subgraph B of Kₙ has a 1-dependent set of size l or the subgraph R has a 1-dependent set of size m. The 2-edge colouring (R,B) is a t₁(l,m) Ramsey colouring of Kₙ if B (R, respectively) does not contain a 1-dependent set of size l (m, respectively); in this...

On 2 -extendability of generalized Petersen graphs

Nirmala B. Limaye, Mulupuri Shanthi C. Rao (1996)

Mathematica Bohemica

Let G P ( n , k ) be a generalized Petersen graph with ( n , k ) = 1 , n > k 4 . Then every pair of parallel edges of G P ( n , k ) is contained in a 1-factor of G P ( n , k ) . This partially answers a question posed by Larry Cammack and Gerald Schrag [Problem 101, Discrete Math. 73(3), 1989, 311-312].

On a family of cubic graphs containing the flower snarks

Jean-Luc Fouquet, Henri Thuillier, Jean-Marie Vanherpe (2010)

Discussiones Mathematicae Graph Theory

We consider cubic graphs formed with k ≥ 2 disjoint claws C i K 1 , 3 (0 ≤ i ≤ k-1) such that for every integer i modulo k the three vertices of degree 1 of C i are joined to the three vertices of degree 1 of C i - 1 and joined to the three vertices of degree 1 of C i + 1 . Denote by t i the vertex of degree 3 of C i and by T the set t , t , . . . , t k - 1 . In such a way we construct three distinct graphs, namely FS(1,k), FS(2,k) and FS(3,k). The graph FS(j,k) (j ∈ 1,2,3) is the graph where the set of vertices i = 0 i = k - 1 V ( C i ) T induce j cycles (note that the graphs...

On arbitrarily vertex decomposable unicyclic graphs with dominating cycle

Sylwia Cichacz, Irmina A. Zioło (2006)

Discussiones Mathematicae Graph Theory

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,...,nₖ) of positive integers such that i = 1 k n i = n , there exists a partition (V₁,...,Vₖ) of vertex set of G such that for every i ∈ 1,...,k the set V i induces a connected subgraph of G on n i vertices. We consider arbitrarily vertex decomposable unicyclic graphs with dominating cycle. We also characterize all such graphs with at most four hanging vertices such that exactly two of them have a common neighbour.

On constant-weight TSP-tours

Scott Jones, P. Mark Kayll, Bojan Mohar, Walter D. Wallis (2003)

Discussiones Mathematicae Graph Theory

Is it possible to label the edges of Kₙ with distinct integer weights so that every Hamilton cycle has the same total weight? We give a local condition characterizing the labellings that witness this question's perhaps surprising affirmative answer. More generally, we address the question that arises when "Hamilton cycle" is replaced by "k-factor" for nonnegative integers k. Such edge-labellings are in correspondence with certain vertex-labellings, and the link allows us to determine (up to a constant...

On cyclically embeddable graphs

Mariusz Woźniak (1999)

Discussiones Mathematicae Graph Theory

An embedding of a simple graph G into its complement G̅ is a permutation σ on V(G) such that if an edge xy belongs to E(G), then σ(x)σ(y) does not belong to E(G). In this note we consider some families of embeddable graphs such that the corresponding permutation is cyclic.

On Decomposing Regular Graphs Into Isomorphic Double-Stars

Saad I. El-Zanati, Marie Ermete, James Hasty, Michael J. Plantholt, Shailesh Tipnis (2015)

Discussiones Mathematicae Graph Theory

A double-star is a tree with exactly two vertices of degree greater than 1. If T is a double-star where the two vertices of degree greater than one have degrees k1+1 and k2+1, then T is denoted by Sk1,k2 . In this note, we show that every double-star with n edges decomposes every 2n-regular graph. We also show that the double-star Sk,k−1 decomposes every 2k-regular graph that contains a perfect matching.

On degree sets and the minimum orders in bipartite graphs

Y. Manoussakis, H.P. Patil (2014)

Discussiones Mathematicae Graph Theory

For any simple graph G, let D(G) denote the degree set {degG(v) : v ∈ V (G)}. Let S be a finite, nonempty set of positive integers. In this paper, we first determine the families of graphs G which are unicyclic, bipartite satisfying D(G) = S, and further obtain the graphs of minimum orders in such families. More general, for a given pair (S, T) of finite, nonempty sets of positive integers of the same cardinality, it is shown that there exists a bipartite graph B(X, Y ) such that D(X) = S, D(Y )...

On detectable colorings of graphs

Henry Escuadro, Ping Zhang (2005)

Mathematica Bohemica

Let G be a connected graph of order n 3 and let c E ( G ) { 1 , 2 , ... , k } be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G , the color code of v with respect to c is the k -tuple c ( v ) = ( a 1 , a 2 , , a k ) , where a i is the number of edges incident with v that are colored i ( 1 i k ). The coloring c is detectable if distinct vertices have distinct color codes. The detection number det ( G ) of G is the minimum positive integer k for which G has a detectable k -coloring. We establish a formula for the detection...

Currently displaying 1 – 20 of 82

Page 1 Next