Page 1 Next

## Displaying 1 – 20 of 73

Showing per page

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

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

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

Czechoslovak Mathematical Journal

The split graph ${K}_{r}+\overline{{K}_{s}}$ on $r+s$ vertices is denoted by ${S}_{r,s}$. A non-increasing sequence $\pi =\left({d}_{1},{d}_{2},...,{d}_{n}\right)$ of nonnegative integers is said to be potentially ${S}_{r,s}$-graphic if there exists a realization of $\pi$ containing ${S}_{r,s}$ as a subgraph. In this paper, we obtain a Havel-Hakimi type procedure and a simple sufficient condition for $\pi$ 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 Markov chain approach to randomly grown graphs.

Journal of Applied Mathematics

### A note on degree-continuous graphs

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 note on two circumference generalizations of Chvátal's Hamiltonicity condition

Mathematica Slovaca

### A random graph model for power law graphs.

Experimental Mathematics

### A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs.

The Electronic Journal of Combinatorics [electronic only]

### A spectral bound for graph irregularity

Czechoslovak Mathematical Journal

The imbalance of an edge $e=\left\{u,v\right\}$ in a graph is defined as $i\left(e\right)=|d\left(u\right)-d\left(v\right)|$, where $d\left(·\right)$ is the vertex degree. The irregularity $I\left(G\right)$ 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\left(G\right)\le 4{n}^{3}/27$ (where $n=|V\left(G\right)|$) 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...

### A Turán type problem concerning the powers of the degrees of a graph.

The Electronic Journal of Combinatorics [electronic only]

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

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 entropy proof of the Kahn-Lovász theorem.

The Electronic Journal of Combinatorics [electronic only]

### An extremal problem on potentially ${K}_{p,1,1}$-graphic sequences.

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

### An Implicit Weighted Degree Condition For Heavy Cycles

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...

### Asymptotic comparison of two constructions for large digraphs of given degree and diameter

Acta Mathematica Universitatis Ostraviensis

We compare the asymptotic growth of the order of the digraphs arising from a construction of Comellas and Fiol when applied to Faber-Moore digraphs versus plainly the Faber-Moore digraphs for the corresponding degree and diameter.

### Chromatic number and some multiplicative vertex-degree-based indices of graphs

Kragujevac Journal of Mathematics

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

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}\ge 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.

### Counting triangulations of planar point sets.

The Electronic Journal of Combinatorics [electronic only]

### Degree Equitable Domination on Graphs

Kragujevac Journal of Mathematics

### Degree sequences of $F$-free graphs.

The Electronic Journal of Combinatorics [electronic only]

Page 1 Next