Given two disjoint copies of a graph , denoted and , and a permutation of , the graph is constructed by joining to for all . is said to be a universal fixer if the domination number of is equal to the domination number of for all of . 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.
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 -vertex graph is an injective mapping of integers to to its vertices such that for every edge, the sum of the integers on its endpoints is unique. If equals to , 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...
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...
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....
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...
In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for , the biggest number guaranteeing that there exist graphs on vertices, each two having edit distance at least . By edit distance of two graphs , we mean the number of edges needed to be added to or deleted from graph to obtain graph . This new extremal number is closely linked to the edit distance of graphs. Using probabilistic methods we show that is close...
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...
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...
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.
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.
For a given complex square matrix 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 -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...
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.