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 224

Showing per page

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

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.

Eigenvalue bounds for some classes of matrices associated with graphs

Ranjit Mehatari, M. Rajesh Kannan (2021)

Czechoslovak Mathematical Journal

For a given complex square matrix A with constant row sum, we establish two new eigenvalue inclusion sets. Using these bounds, first, we derive bounds for the second largest and the smallest eigenvalues of adjacency matrices of k -regular graphs. Then we establish some bounds for the second largest and the smallest eigenvalues of the normalized adjacency matrices of graphs and the second smallest and the largest eigenvalues of the Laplacian matrices of graphs. The sharpness of these bounds is verified...

Eigenvalue Conditions for Induced Subgraphs

Jochen Harant, Julia Niebling, Sebastian Richter (2015)

Discussiones Mathematicae Graph Theory

Necessary conditions for an undirected graph G to contain a graph H as induced subgraph involving the smallest ordinary or the largest normalized Laplacian eigenvalue of G are presented.

Currently displaying 41 – 60 of 224