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

Page 1

Displaying 1 – 16 of 16

Showing per page

Packing of three copies of a digraph into the transitive tournament

Monika Pilśniak (2004)

Discussiones Mathematicae Graph Theory

In this paper, we show that if the number of arcs in an oriented graph G (of order n) without directed cycles is sufficiently small (not greater than [2/3] n-1), then there exist arc disjoint embeddings of three copies of G into the transitive tournament TTₙ. It is the best possible bound.

Packing Parameters in Graphs

I. Sahul Hamid, S. Saravanakumar (2015)

Discussiones Mathematicae Graph Theory

In a graph G = (V,E), a non-empty set S ⊆ V is said to be an open packing set if no two vertices of S have a common neighbour in G. An open packing set which is not a proper subset of any open packing set is called a maximal open packing set. The minimum and maximum cardinalities of a maximal open packing set are respectively called the lower open packing number and the open packing number and are denoted by ρoL and ρo. In this paper, we present some bounds on these parameters.

Paths with restricted degrees of their vertices in planar graphs

Stanislav Jendroľ (1999)

Czechoslovak Mathematical Journal

In this paper it is proved that every 3 -connected planar graph contains a path on 3 vertices each of which is of degree at most 15 and a path on 4 vertices each of which has degree at most 23 . Analogous results are stated for 3 -connected planar graphs of minimum degree 4 and 5 . Moreover, for every pair of integers n ≥ 3 , k ≥ 4 there is a 2 -connected planar graph such that every path on n vertices in it has a vertex of degree k .

Pₘ-saturated bipartite graphs with minimum size

Aneta Dudek, A. Paweł Wojda (2004)

Discussiones Mathematicae Graph Theory

A graph G is said to be H-saturated if G is H-free i.e., (G has no subgraph isomorphic to H) and adding any new edge to G creates a copy of H in G. In 1986 L. Kászonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size sat(n;Pₘ) of Pₘ-saturated graph of order n. They gave the number sat(n;Pₘ) for n big enough. We deal with similar problem for bipartite graphs.

Potentially H-bigraphic sequences

Michael Ferrara, Michael Jacobson, John Schmitt, Mark Siggers (2009)

Discussiones Mathematicae Graph Theory

We extend the notion of a potentially H-graphic sequence as follows. Let A and B be nonnegative integer sequences. The sequence pair S = (A,B) is said to be bigraphic if there is some bipartite graph G = (X ∪ Y,E) such that A and B are the degrees of the vertices in X and Y, respectively. If S is a bigraphic pair, let σ(S) denote the sum of the terms in A. Given a bigraphic pair S, and a fixed bipartite graph H, we say that S is potentially H-bigraphic if there is some realization of S containing...

Potentially K m - G -graphical sequences: A survey

Chunhui Lai, Lili Hu (2009)

Czechoslovak Mathematical Journal

The set of all non-increasing nonnegative integer sequences π = ( d ( v 1 ) , d ( v 2 ) , ⋯ , d ( v n ) ) is denoted by NS n . A sequence π ∈ NS n is said to be graphic if it is the degree sequence of a simple graph G on n vertices, and such a graph G is called a realization of π . The set of all graphic sequences in NS n is denoted by GS n . A graphical sequence π is potentially H -graphical if there is a realization of π containing H as a subgraph, while π is forcibly H -graphical if every realization of π contains H as a subgraph. Let K k denote a complete...

Currently displaying 1 – 16 of 16

Page 1