For a finite, simple, undirected graph G=(V(G),E(G)), an open-dominating set S⊆V(G) is such that every vertex in G has at least one neighbor in S. An open-independent, open-locating-dominating set ...S⊆V(G) (OLDoind-set for short) is such that no two vertices in G have the same set of neighbors in S and each vertex in S is open-dominated exactly once by S. The problem of deciding whether or not G has such set is known to be NP-complete. The complementary prism of G is the graph GG¯, formed from the disjoint union of G and its complement G¯ by adding the edges of a perfect matching between the corresponding vertices of G and G¯. Various properties, upper bounds and logarithmic lower bounds on the sizes of minimal OLDoind-sets in complementary prisms are presented. We show that deciding, for a given graph G, whether or not GG¯ has an OLDoind-set is an NP-complete problem. On the other hand, if the girth of G is at least four, we show that the OLDoind-set of GG¯, if it exists, can be found in polynomial time.
The total domination numberγt(G) of a graph G is the cardinality of a smallest vertex subset D of V(G) such that each vertex of G has at least one neighbor in D. The annihilation numbera(G) of G is ...the largest integer k such that there exist k different vertices in G with degree sum of at most the size of G. It is conjectured that γt(G)≤a(G)+1 holds for every nontrivial connected graph G. The conjecture was proved for graphs with minimum degree at least 3, and some graphs with minimum degree 1 or 2. In this paper, we prove that the above conjecture holds for some graphs with minimum degree at most two. More specifically, we prove that the above conjecture holds for inflated graphs of trees, square graphs of trees, maximal outerplanar graphs and complementary prisms of graphs.
A set S ⊆ V (G) is a hop dominating set of G if for each v ∈ V (G) \ S, there exists w ∈ S such that dG(v, w) = 2. It is a global hop dominating set of G if it is a hop dominating set of both G ...and the complement of G. The minimum cardinality of a hop dominating (global hop dominating) set of G, denoted by γh(G)(resp.γgh(G)), is called the hop domination (resp. global hop domination) number of G. In this paper, we give some realization results involving domination, hop domination, and global hop domination parameters. Also, we give a rectification of a result found in a recent paper of the authors and use this to prove some results in this paper. Â
In this paper, we revisit the concept of (normalized) closeness centrality of a vertex in a graph and investigate it in some graphs under some operations. Specifically, we derive formulas that ...compute the closeness centrality of vertices in the shadow graph, complementary prism, edge corona, and disjunction of graphs.
A set D ⊆ (G) is an independent transversal dominating set of G if D is a dominating set and also intersects every maximum independent set in G. The minimum cardinality of such a set is equal to the ...transversal domination number, denoted by □it(G). This paper is devoted to the computation of the independent transversal domination number of some complementary prism.
The general position number gp(G) of a graph G is the cardinality of a largest set of vertices S such that no element of S lies on a geodesic between two other elements of S. The complementary prism ...G G ¯ of G is the graph formed from the disjoint union of G and its complement G ¯ by adding the edges of a perfect matching between them. It is proved that gp(G G ¯ ) ≤ n(G) + 1 if G is connected and gp(G G ¯ ) ≤ n(G) if G is disconnected. Graphs G for which gp(G G ¯ ) = n(G) + 1 holds, provided that both G and G ¯ are connected, are characterized. A sharp lower bound on gp(G G ¯ ) is proved. If G is a connected bipartite graph or a split graph then gp(G G ¯ ) ∈ {n(G), n(G)+1}. Connected bipartite graphs and block graphs for which gp(G G ¯ ) = n(G) + 1 holds are characterized. A family of block graphs is constructed in which the gp-number of their complementary prisms is arbitrary smaller than their order.
On the geodetic number of complementary prisms Castonguay, Diane; Coelho, Erika M.M.; Coelho, Hebert ...
Information processing letters,
April 2019, 2019-04-00, Letnik:
144
Journal Article
Recenzirano
Motivated by previous work, we prove that, given a graph G and a positive integer k, deciding whether the geodetic number of the complementary prism of G is at most k is an NP-complete problem. We ...also show lower and upper bounds for the geodetic number of a complementary prism, and determine the geodetic number of a complementary prism when it is defined over a split graph.
•Geodetic number is NP-complete for complementary prisms.•Determined the geodetic number for complementary prisms of split graphs.•Presented bounds on the geodetic number for complementary prisms.
The complementary prism GG¯ of a graph G arises from the disjoint union of G and the complement G¯ of G by adding a perfect matching joining corresponding pairs of vertices in G and G¯. Partially ...answering a question posed by Haynes et al. (2007) we provide an efficient characterization of the circumference of the complementary prism TT¯ of a tree T and show that TT¯ has cycles of all lengths between 3 and its circumference. Furthermore, we prove that for a given graph of bounded maximum degree it can be decided in polynomial time whether its complementary prism is Hamiltonian.
The t-admissibility problem aims to decide whether a graph G has a spanning tree T in which the distance between any two adjacent vertices of G is at most t. In this case, G is called t-admissible, ...and the smallest t for which G is t-admissible is the stretch index of G. A complementary prism of G, denoted by GG¯, is obtained by the union of G with its complement G¯ and the addition of a perfect matching between corresponding vertices of G and G¯. One of the challenges of the t-admissibility problem is to determine 3-admissible graph classes, since the computational complexity of such a problem remains open for more than 25 years. Moreover, it is known that recognizing 4-admissible graphs is, in general, an NP-complete problem (Cai and Corneil, 1995), as well as recognizing t-admissible graphs for graphs with diameter at most t+1, for t≥4 (Papoutsakis, 2013). We prove that any graph G, non-complete graph, can be transformed into a 4-admissible one, by obtaining GG¯. Furthermore, we prove that the stretch indexes of GG¯ graphs are equal to 4, and since they have diameter at most t+1, we present a class for which t-admissibility is solved in polynomial time. GG graphs are the Cartesian product G×K2, defined by the union of two copies of G and the addition of a perfect matching between corresponding vertices of the two graphs G. Interestingly, we prove that for GG graphs, whose definition is very similar to GG¯’s, t-admissibility is NP-complete. Generalizing these constructions, we prove that determining t-admissibility is NP-complete for graphs that have perfect matching.
PDF
