Page 1 Next

Displaying 1 – 20 of 22

Showing per page

Edge cycle extendable graphs

Terry A. McKee (2012)

Discussiones Mathematicae Graph Theory

A graph is edge cycle extendable if every cycle C that is formed from edges and one chord of a larger cycle C⁺ is also formed from edges and one chord of a cycle C' of length one greater than C with V(C') ⊆ V(C⁺). Edge cycle extendable graphs are characterized by every block being either chordal (every nontriangular cycle has a chord) or chordless (no nontriangular cycle has a chord); equivalently, every chord of a cycle of length five or more has a noncrossing chord.

Edge maximal C 2 k + 1 -edge disjoint free graphs

M.S.A. Bataineh, M.M.M. Jaradat (2012)

Discussiones Mathematicae Graph Theory

For two positive integers r and s, 𝓖(n;r,s) denotes to the class of graphs on n vertices containing no r of s-edge disjoint cycles and f(n;r,s) = max{𝓔(G):G ∈ 𝓖(n;r,s)}. In this paper, for integers r ≥ 2 and k ≥ 1, we determine f(n;r,2k+1) and characterize the edge maximal members in 𝓖(n;r,2k+1).

Edge-disjoint odd cycles in graphs with small chromatic number

Claude Berge, Bruce Reed (1999)

Annales de l'institut Fourier

For a simple graph, we consider the minimum number of edges which block all the odd cycles and the maximum number of odd cycles which are pairwise edge-disjoint. When these two coefficients are equal, interesting consequences appear. Similar problems (but interchanging “vertex-disjoint odd cycles” and “edge-disjoint odd cycles”) have been considered in a paper by Berge and Fouquet.

Edge-disjoint paths in permutation graphs

C. P. Gopalakrishnan, C. Pandu Rangan (1995)

Discussiones Mathematicae Graph Theory

In this paper we consider the following problem. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two edge-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂, respectively. We give a linear (O(|V|+|E|)) algorithm to solve this problem on a permutation graph.

Efficient algorithms for minimal disjoint path problems on chordal graphs

C.P. Gopalakrishnan, C.R. Satyan, C. Pandu Rangan (1995)

Discussiones Mathematicae Graph Theory

Disjoint paths have applications in establishing bottleneck-free communication between processors in a network. The problem of finding minimum delay disjoint paths in a network directly reduces to the problem of finding the minimal disjoint paths in the graph which models the network. Previous results for this problem on chordal graphs were an O(|V| |E|²) algorithm for 2 edge disjoint paths and an O(|V| |E|) algorithm for 2 vertex disjoint paths. In this paper, we give an O(|V| |E|) algorithm for...

End-faithful spanning trees of countable graphs with prescribed sets of rays

Norbert Polat (2001)

Czechoslovak Mathematical Journal

We prove that a countable connected graph has an end-faithful spanning tree that contains a prescribed set of rays whenever this set is countable, and we show that this solution is, in a certain sense, the best possible. This improves a result of Hahn and Širáň Theorem 1.

Exact 2 -step domination in graphs

Gary Chartrand, Frank Harary, Moazzem Hossain, Kelly Schultz (1995)

Mathematica Bohemica

For a vertex v in a graph G , the set N 2 ( v ) consists of those vertices of G whose distance from v is 2. If a graph G contains a set S of vertices such that the sets N 2 ( v ) , v S , form a partition of V ( G ) , then G is called a 2 -step domination graph. We describe 2 -step domination graphs possessing some prescribed property. In addition, all 2 -step domination paths and cycles are determined.

Currently displaying 1 – 20 of 22

Page 1 Next