A number of problems in mobile computing, group-based collaboration, automated theorem proving, networking, scheduling, and cluster analysis suggested the study of graphs featuring certain "local density" ch...
详细信息
A number of problems in mobile computing, group-based collaboration, automated theorem proving, networking, scheduling, and cluster analysis suggested the study of graphs featuring certain "local density" characteristics. Typically, the notion of local density is equated with the absence of chordless paths of length three or more. Recently, a new metric for local density has been proposed, allowing a number of such induced paths to occur. More precisely, a graph G is called p4-sparse if no set of five vertices in G induces more than one chordless path of length three. p4-sparse graphs generalize the well-known class of cographs corresponding to a more stringent local density metric. One remarkable feature of p4-sparse graphs is that they admit a tree representation unique up to isomorphism. In this work we present a parallel algorithm to recognize p4-sparse graphs and show how the data structures returned by the recognition algorithm can be used to construct the corresponding tree representation. With a graph G=(V,E) with \V\=n and \E\=m as input, our algorithms run in O(log n) time using O((n(2) + mn)/log n) processors in the EREW-pRAM model.
A graph G is p4-sparse if no set of five vertices in G induces more than one chordless path of length three. p4-sparse graphs generalize both the class of cographs and the class of p4-reducible graphs. One remarkable ...
详细信息
A graph G is p4-sparse if no set of five vertices in G induces more than one chordless path of length three. p4-sparse graphs generalize both the class of cographs and the class of p4-reducible graphs. One remarkable feature of p4-sparse graphs is that they admit a tree representation unique up to isomorphism. It has been shown that this tree representation can be obtained in polynomial time. This paper gives a linear time algorithm to recognize p4-sparse graphs and shows how the data structures returned by the recognition algorithm can be used to construct the corresponding tree representation in linear time.
Given a graph G = (V, E ), a function f : V -> { 0 , 1, 2} is said to be a Roman Dominating function if for every v E V with f ( v ) = 0, there exists a vertex u E N ( v ) such that f (u) = 2. A Roman Dominating fu...
详细信息
Given a graph G = (V, E ), a function f : V -> { 0 , 1, 2} is said to be a Roman Dominating function if for every v E V with f ( v ) = 0, there exists a vertex u E N ( v ) such that f (u) = 2. A Roman Dominating function f is said to be an Independent Roman Dominating function (or IRDF), if V 1 boolean OR V 2 forms an independent set, where V i = {v E V | f ( v ) = i } , for i E { 0 , 1, 2}. The total weight off is equal to & sum;vEV f ( v ), and is denoted as w ( f ). The Independent Roman Domination Number of G, denoted by iR(G), is defined as min{w(f ) | f is an IRDF of G }. For a given graph G , the problem of computing i R ( G ) is defined as the Minimum Independent Roman Domination problem. The problem is already known to be Np-hard for bipartite graphs. In this paper, we further study the algorithmic complexity of the problem. In this paper, we propose a polynomial-time algorithm to solve the Minimum Independent Roman Domination problem for distance-hereditary graphs, split graphs, and p4-sparsegraphs. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
A graph G was defined in [16] as p-4-reducible, if no vertex in G belongs to more than one chordless path on four vertices or p-4. A graph G is defined in [15] as p-4-sparse if no set of five vertices induces more tha...
详细信息
A graph G was defined in [16] as p-4-reducible, if no vertex in G belongs to more than one chordless path on four vertices or p-4. A graph G is defined in [15] as p-4-sparse if no set of five vertices induces more than one p-4 in G. p-4-sparsegraphs generalize both p-4-reducible and the well known class of p-4-free graphs or cographs. In an extended abstract in [11] the first author introduced a method using the modular decomposition tree of a graph as the framework for the resolution of algorithmic problems. This method was applied to the study of p-4-sparse and extended p-4-sparsegraphs. In this paper, we begin by presenting the complete information about the method used in [11]. We propose a unique tree representation of p-4-sparse and a unique tree representation of p-4-reducible graphs leading to a simple linear recognition algorithm for both classes of graphs. In this way we simplify and unify the solutions for these problems, presented in [16-19]. The tree representation of an n-vertex p-4-sparse or a p-4-reducible graph is the key for obtaining O(n) time algorithms for the weighted version of classical optimization problems solved in [20]. These problems are Np-complete on general graphs. Finally, by relaxing the restriction concerning the exclusion of the C-5 cycles from p-4-sparse and p-4-reducible graphs, we introduce the class of the extended p-4-sparse and the class of the extended p-4-reducible graphs. We then show that a minimal amount of additional work suffices for extending most of our algorithms to these new classes of graphs.
A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of G is the maximum integer for which G has a b...
详细信息
A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of G is the maximum integer for which G has a b-coloring with colors. A graph G is b-continuous if G has a b-coloring with k colors, for every integer k in the interval . It is known that not all graphs are b-continuous. Here, we investigate whether the lexicographic product G[H] of b-continuous graphs G and H is also b-continuous. Using homomorphisms, we provide a new lower bound for , namely , where , and prove that if is b-continuous for every positive integer , then G[H] admits a b-coloring with k colors, for every k in the interval . We also prove that is b-continuous, for every positive integer , whenever G is a -sparse graph, and we give further results on the b-spectrum of , when G is chordal. Finally, we determine the value of , when T is a tree.
暂无评论