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 3 Next

Displaying 41 – 60 of 362

Showing per page

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

Edit distance measure for graphs

Tomasz Dzido, Krzysztof Krzywdziński (2015)

Czechoslovak Mathematical Journal

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for g ( n , l ) , the biggest number k guaranteeing that there exist l graphs on n vertices, each two having edit distance at least k . By edit distance of two graphs G , F we mean the number of edges needed to be added to or deleted from graph G to obtain graph F . This new extremal number g ( n , l ) is closely linked to the edit distance of graphs. Using probabilistic methods we show that g ( n , l ) is close...

Editorial

Irina Perfilieva, Michael Wagenknecht (2009)

Acta Mathematica Universitatis Ostraviensis

Edon- ℛ ( 256 , 384 , 512 ) – an efficient implementation of Edon- ℛ family of cryptographic hash functions

Danilo Gligoroski, Svein Johan Knapskog (2008)

Commentationes Mathematicae Universitatis Carolinae

We have designed three fast implementations of a recently proposed family of hash functions Edon– ℛ . They produce message digests of length n = 256 , 384 , 512 bits and project security of 2 n 2 hash computations for finding collisions and 2 n hash computations for finding preimages and second preimages. The design is not the classical Merkle-Damgård but can be seen as wide-pipe iterated compression function. Moreover the design is based on using huge quasigroups of orders 2 256 , 2 384 and 2 512 that are constructed by using only bitwise...

Effect of edge-subdivision on vertex-domination in a graph

Amitava Bhattacharya, Gurusamy Rengasamy Vijayakumar (2002)

Discussiones Mathematicae Graph Theory

Let G be a graph with Δ(G) > 1. It can be shown that the domination number of the graph obtained from G by subdividing every edge exactly once is more than that of G. So, let ξ(G) be the least number of edges such that subdividing each of these edges exactly once results in a graph whose domination number is more than that of G. The parameter ξ(G) is called the subdivision number of G. This notion has been introduced by S. Arumugam and S. Velammal. They have conjectured that for any graph G with...

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

Efficient (j,k)-domination

Robert R. Rubalcaba, Peter J. Slater (2007)

Discussiones Mathematicae Graph Theory

A dominating set S of a graph G is called efficient if |N[v]∩ S| = 1 for every vertex v ∈ V(G). That is, a dominating set S is efficient if and only if every vertex is dominated exactly once. In this paper, we investigate efficient multiple domination. There are several types of multiple domination defined in the literature: k-tuple domination, {k}-domination, and k-domination. We investigate efficient versions of the first two as well as a new type of multiple domination.

Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs

Krzysztof Giaro, Marek Kubale (2009)

Discussiones Mathematicae Graph Theory

We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers and to their multicolorings.

Currently displaying 41 – 60 of 362