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 – 5 of 5

Showing per page

Edge-connectivity of strong products of graphs

Bostjan Bresar, Simon Spacapan (2007)

Discussiones Mathematicae Graph Theory

The strong product G₁ ⊠ G₂ of graphs G₁ and G₂ is the graph with V(G₁)×V(G₂) as the vertex set, and two distinct vertices (x₁,x₂) and (y₁,y₂) are adjacent whenever for each i ∈ 1,2 either x i = y i or x i y i ∈ E ( G i ) . In this note we show that for two connected graphs G₁ and G₂ the edge-connectivity λ (G₁ ⊠ G₂) equals minδ(G₁ ⊠ G₂), λ(G₁)(|V(G₂)| + 2|E(G₂)|), λ(G₂)(|V(G₁)| + 2|E(G₁)|). In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.

Erdős regular graphs of even degree

Andrey A. Dobrynin, Leonid S. Mel'nikov, Artem V. Pyatkin (2007)

Discussiones Mathematicae Graph Theory

In 1960, Dirac put forward the conjecture that r-connected 4-critical graphs exist for every r ≥ 3. In 1989, Erdös conjectured that for every r ≥ 3 there exist r-regular 4-critical graphs. A method for finding r-regular 4-critical graphs and the numbers of such graphs for r ≤ 10 have been reported in [6,7]. Results of a computer search for graphs of degree r = 12,14,16 are presented. All the graphs found are both r-regular and r-connected.

Currently displaying 1 – 5 of 5

Page 1