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.
Given a finite simple graph Γ on n vertices its complementary prism is the graph ΓΓ¯ that is obtained from Γ and its complement Γ¯ by adding a perfect matching where each its edge connects two copies ...of the same vertex in Γ and Γ¯. It generalizes the Petersen graph, which is obtained if Γ is the pentagon. The automorphism group of ΓΓ¯ is described for an arbitrary graph Γ. In particular, it is shown that the ratio between the cardinalities of the automorphism groups of ΓΓ¯ and Γ can attain only the values 1, 2, 4, and 12. It is shown that ΓΓ¯ is vertex-transitive if and only if Γ is vertex-transitive and self-complementary. Moreover, the complementary prism is not a Cayley graph whenever n>1.
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.