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

Previous Page 2 Next

Displaying 21 – 40 of 224

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.

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.

Edge-domatic numbers of cacti

Bohdan Zelinka (1991)

Mathematica Bohemica

The edge-domatic number of a graph is the maximum number of classes of a partition of its edge set into dominating sets. This number is studied for cacti, i.e. graphs in which each edge belongs to at most one circuit.

Edgeless graphs are the only universal fixers

Kirsti Wash (2014)

Czechoslovak Mathematical Journal

Given two disjoint copies of a graph G , denoted G 1 and G 2 , and a permutation π of V ( G ) , the graph π G is constructed by joining u ∈ V ( G 1 ) to π ( u ) ∈ V ( G 2 ) for all u ∈ V ( G 1 ) . G is said to be a universal fixer if the domination number of π G is equal to the domination number of G for all π of V ( G ) . In 1999 it was conjectured that the only universal fixers are the edgeless graphs. Since then, a few partial results have been shown. In this paper, we prove the conjecture completely.

Edge-sum distinguishing labeling

Jan Bok, Nikola Jedličková (2021)

Commentationes Mathematicae Universitatis Carolinae

We study edge-sum distinguishing labeling, a type of labeling recently introduced by Z. Tuza (2017) in context of labeling games. An ESD labeling of an n -vertex graph G is an injective mapping of integers 1 to l to its vertices such that for every edge, the sum of the integers on its endpoints is unique. If l equals to n , we speak about a canonical ESD labeling. We focus primarily on structural properties of this labeling and show for several classes of graphs if they have or do not have a canonical...

Edge-Transitive Lexicographic and Cartesian Products

Wilfried Imrich, Ali Iranmanesh, Sandi Klavžar, Abolghasem Soltani (2016)

Discussiones Mathematicae Graph Theory

In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product G ◦ H of a connected graph G that is not complete by a graph H, we show that it is edge-transitive if and only if G is edge-transitive and H is edgeless. If the first factor of G ∘ H is non-trivial and complete, then G ∘ H is edge-transitive if and only if H is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao...

Edge-Transitivity of Cayley Graphs Generated by Transpositions

Ashwin Ganesan (2016)

Discussiones Mathematicae Graph Theory

Let S be a set of transpositions generating the symmetric group Sn (n ≥ 5). The transposition graph of S is defined to be the graph with vertex set {1, . . . , n}, and with vertices i and j being adjacent in T(S) whenever (i, j) ∈ S. In the present note, it is proved that two transposition graphs are isomorphic if and only if the corresponding two Cayley graphs are isomorphic. It is also proved that the transposition graph T(S) is edge-transitive if and only if the Cayley graph Cay(Sn, S) is edge-transitive....

Edit distance between unlabeled ordered trees

Anne Micheli, Dominique Rossin (2006)

RAIRO - Theoretical Informatics and Applications

There exists a bijection between one-stack sortable permutations (permutations which avoid the pattern (231)) and rooted plane trees. We define an edit distance between permutations which is consistent with the standard edit distance between trees. This one-to-one correspondence yields a polynomial algorithm for the subpermutation problem for (231) pattern-avoiding permutations. Moreover, we obtain the generating function of the edit distance between ordered unlabeled trees and some special ones. For...

Currently displaying 21 – 40 of 224