Page 1 Next

Displaying 1 – 20 of 73

Showing per page

A Constructive Extension of the Characterization on PotentiallyK s , t -Bigraphic Pairs

Ji-Yun Guo, Jian-Hua Yin (2017)

Discussiones Mathematicae Graph Theory

Let Ks,t be the complete bipartite graph with partite sets of size s and t. Let L1 = ([a1, b1], . . . , [am, bm]) and L2 = ([c1, d1], . . . , [cn, dn]) be two sequences of intervals consisting of nonnegative integers with a1 ≥ a2 ≥ . . . ≥ am and c1 ≥ c2 ≥ . . . ≥ cn. We say that L = (L1; L2) is potentially Ks,t (resp. As,t)-bigraphic if there is a simple bipartite graph G with partite sets X = {x1, . . . , xm} and Y = {y1, . . . , yn} such that ai ≤ dG(xi) ≤ bi for 1 ≤ i ≤ m, ci ≤ dG(yi) ≤ di for...

A Different Short Proof of Brooks’ Theorem

Landon Rabern (2014)

Discussiones Mathematicae Graph Theory

Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.

A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially S r , s -graphic

Jian Hua Yin (2012)

Czechoslovak Mathematical Journal

The split graph K r + K s ¯ on r + s vertices is denoted by S r , s . A non-increasing sequence π = ( d 1 , d 2 , ... , d n ) of nonnegative integers is said to be potentially S r , s -graphic if there exists a realization of π containing S r , s as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for π to be potentially S r , s -graphic. They are extensions of two theorems due to A. R. Rao (The clique number of a graph with given degree sequence, Graph Theory, Proc. Symp., Calcutta 1976, ISI Lect. Notes Series...

A note on degree-continuous graphs

Chiang Lin, Wei-Bo Ou (2007)

Czechoslovak Mathematical Journal

The minimum orders of degree-continuous graphs with prescribed degree sets were investigated by Gimbel and Zhang, Czechoslovak Math. J. 51 (126) (2001), 163–171. The minimum orders were not completely determined in some cases. In this note, the exact values of the minimum orders for these cases are obtained by giving improved upper bounds.

A spectral bound for graph irregularity

Felix Goldberg (2015)

Czechoslovak Mathematical Journal

The imbalance of an edge e = { u , v } in a graph is defined as i ( e ) = | d ( u ) - d ( v ) | , where d ( · ) is the vertex degree. The irregularity I ( G ) of G is then defined as the sum of imbalances over all edges of G . This concept was introduced by Albertson who proved that I ( G ) 4 n 3 / 27 (where n = | V ( G ) | ) and obtained stronger bounds for bipartite and triangle-free graphs. Since then a number of additional bounds were given by various authors. In this paper we prove a new upper bound, which improves a bound found by Zhou and Luo in 2008. Our bound involves the...

Acyclic 6-Colouring of Graphs with Maximum Degree 5 and Small Maximum Average Degree

Anna Fiedorowicz (2013)

Discussiones Mathematicae Graph Theory

A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, . . . , k} of colours such that adjacent vertices receive distinct colours. Such a k-colouring is called acyclic, if for every two distinct colours i and j, the subgraph induced by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, every cycle in G has at least three distinct colours. Acyclic colourings were introduced by Gr¨unbaum in 1973, and since then have...

An Implicit Weighted Degree Condition For Heavy Cycles

Junqing Cai, Hao Li, Wantao Ning (2014)

Discussiones Mathematicae Graph Theory

For a vertex v in a weighted graph G, idw(v) denotes the implicit weighted degree of v. In this paper, we obtain the following result: Let G be a 2-connected weighted graph which satisfies the following conditions: (a) The implicit weighted degree sum of any three independent vertices is at least t; (b) w(xz) = w(yz) for every vertex z ∈ N(x) ∩ N(y) with xy /∈ E(G); (c) In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains...

Chvátal's Condition cannot hold for both a graph and its complement

Alexandr V. Kostochka, Douglas B. West (2006)

Discussiones Mathematicae Graph Theory

Chvátal’s Condition is a sufficient condition for a spanning cycle in an n-vertex graph. The condition is that when the vertex degrees are d₁, ...,dₙ in nondecreasing order, i < n/2 implies that d i > i or d n - i n - i . We prove that this condition cannot hold in both a graph and its complement, and we raise the problem of finding its asymptotic probability in the random graph with edge probability 1/2.

Currently displaying 1 – 20 of 73

Page 1 Next