ALGORITHMIC COMPLEXITY OF ISOLATE SECURE DOMINATION IN GRAPHS

ALGORITHMIC COMPLEXITY OF ISOLATE SECURE DOMINATION IN GRAPHS

J. P. Kumar, P. V. S. Reddy

[PDF]

Abstract

A dominating set S is an Isolate Dominating Set (IDS) if the induced sub- graph G[S] has at least one isolated vertex. In this paper, we initiate the study of new domination parameter called, isolate secure domination. An isolate dominating set S ⊆ V is an isolate secure dominating set (ISDS), if for each vertex u ∈ V \ S, there exists a neighboring vertex v of u in S such that (S \{v})∪{u} is an IDS of G. The minimum cardinality of an ISDS of G is called as an isolate secure domination number, and is denoted by γ0s(G). We give isolate secure domination number of path and cycle graphs. Given a graph G = (V,E) and a positive integer k, the ISDM problem is to check whether G has an isolate secure dominating set of size at most k. We prove that ISDM is NP-complete even when restricted to bipartite graphs and split graphs. We also show that ISDM can be solved in linear time for graphs of bounded tree-width.

Keywords

Domination, NP-complete, Secure domination, CMSOL, Isolate domination

BALANCED RANK DISTRIBUTION LABELING OF LADDER GRAPHS, COMPLETE GRAPHS AND COMPLETE BIPARTITE GRAPHS

BALANCED RANK DISTRIBUTION LABELING OF LADDER GRAPHS, COMPLETE GRAPHS AND COMPLETE BIPARTITE GRAPHS

P. Hemalatha, S. Gokilamani

[PDF]

Abstract

A balanced rank distribution labeling of a graph G of order n is a new kind of vertex labeling from {1, 2, 3, ..., k}(n ≤ k ∈ Z+) which leads to a balanced edge labeling of G called edge ranks. In this paper, the balanced rank distribution labeling of ladder graphs Ln/2 for even n ≥ 6, complete graphs Kn for n ≥ 3 and complete bipartite graphs Kn/2,n/2 for even n ≥ 4 have been investigated and obtained the results on balanced rank distribution number (brd(G)) for the given graphs as follows:

(i) brd(Ln/2)=3n−15,forevenn≥12
(ii) brd(Kn)=n,forn≥3
(iii) brd(Kn/2,n/2) = n, for even n ≥ 4

Keywords

Labeling of graphs, Balanced rank distribution labeling, Edge ranking, Bal- anced rank distribution number, Strongly and Weakly balanced rank distribution graphs.

EDGE-VERTEX DOMINATION AND TOTAL EDGE DOMINATION IN TREES

EDGE-VERTEX DOMINATION AND TOTAL EDGE DOMINATION IN TREES

H. N. Kumar, Y. B. Venkatakrishnan

[PDF]

Abstract

An edge e ∈ E(G) dominates a vertex v ∈ V (G) if e is incident with v or e is incident with a vertex adjacent to v. An edge-vertex dominating set of a graph G is a set D of edges of G such that every vertex of G is edge-vertex dominated by an edge of D. The edge-vertex domination number of a graph G is the minimum cardinality of an edge-vertex dominating set of G. A subset D ⊆ E(G) is a total edge dominating set of G if every edge of G has a neighbor in D. The total edge domination number of G is the minimum cardinality of a total edge dominating set of G. We characterize all trees with total edge domination number equal to edge-vertex domination number.

Keywords

Edge-vertex domination, Total Edge Domination, Tree.

I-CORDIAL LABELING OF SPIDER GRAPHS

I-CORDIAL LABELING OF SPIDER GRAPHS

S. Sriram, K. Thirusangu

[PDF]

Abstract

Let G= (V, E) be a graph with p vertices and q edges. A graph G=(V,E)with p vertices and q edges is said to be an I-cordial labeling of a graph if there exists an injective map f from as p is even or odd respectively such 2222 that the injective mapping is defined for f(u) + f(v) ̸= 0 that induces an edge labeling f∗ : E→{0, 1} where f∗(uv) = 1 if f(u) + f(v) > 0 and f∗(uv) = 0 otherwise, such that the number of edges labeled with 1 and the number of edges labeled with 0 differ atmost by 1. If a graph satisfies the condition then graph is called I-Cordial labeling graph or I - Cordial graph. In this paper we intend to prove the spider graph SP(1m,2t) is integer I-cordial labeling graph and obtain some characteristics of I cordial labeling on the graph and we define M-Joins of Spider graph SP(1m,2t) and study their characteristics. Here we use the notation ⌊−p..p⌋∗ = ⌊−p..p⌋ − [0] and ⌊−p..p⌋ = [x/x is an integer such that | x |≤ p]

Keywords

Cordial Labeling of graphs, I-Cordial labeling of graphs, Spider graphs

A HYBRID COMBINATION OF SUBSTITUTION AND TRANSPOSITION CIPHERS FOR EFFICIENT ENCRYPTION USING GRAPH LABELING

A HYBRID COMBINATION OF SUBSTITUTION AND TRANSPOSITION CIPHERS FOR EFFICIENT ENCRYPTION USING GRAPH LABELING

V. N. J. Shruthy, V. Maheswari

[PDF]

Abstract

In this study, we conceptualise a hybrid approach of plaintext encryption by making use of Substitution and Transposition cipher technique namely Playfair Cipher and Simple Columnar Transposition. Both the Ciphers are Symmetric Encryption Tech- nique and the need for developing such a hybrid is to inherit the positive traits as well as restrict certain limitations of both the techniques to a considerable extent. The resulting hybrid text is further subjected to Graph Labeling Technique as the receiver receives the ciphertext in the form of a Graph structure together with a clue to determine the type of labeling used and the ciphertext sequence. Here we adopt two varied labeling techniques namely Simply Sequentially Additive labeling and Distance two labeling for some Tree related Graphs and the corresponding Decryption of the Cipher Graph yields the desired plaintext.

Keywords

Playfair Cipher, Simple Columnar transposition, Hybrid text, Simply Se- quentially Additive labeling, Distance Two labeling, Cipher Graph.

THE MINIMUM MEAN MONOPOLY ENERGY OF A GRAPH

THE MINIMUM MEAN MONOPOLY ENERGY OF A GRAPH

M. V. Chakradhara Rao, K. A. Venkatesh, D. V. Lakshmi

[PDF]

Abstract

The motivation for the study of the graph energy comes from chemistry, where the research on the so-called total π - electron energy can be traced back until the 1930s. This graph invariant is very closely connected to a chemical quantity known as the total π - electron energy of conjugated hydro carbon molecules. In recent times analogous energies are being considered, based on Eigen values of a variety of other graph matrices. In 1978, I.Gutman [1] defined energy mathematically for all graphs. Energy of graphs has many mathematical properties which are being investigated. The ordinary energy of an undirected simple finite graph G is defined as the sum of the absolute val- ues of the Eigen values of its associated matrix. i.e. if μ1, μ2, ..., μn are the Eigen values of adjacency matrix A(G), then energy of graph is E(G) = ni=1 |μi|. Laura Buggy, Amalia Culiuc, Katelyn Mccall and Duyguyen [9] introduced the more general M-energy or Mean Energy of G is then defined as EM (G) = ni=1 |μi − μ ̄|, where μ ̄ is the average of μ1, μ2, ..., μn. A subset M ⊆ V (G), in a graph G (V, E), is called a monopoly set of G if every vertex v ∈ (V - M) has at least d(v) neighbors in M. The minimum cardinality of a monopoly set 2 among all monopoly sets in G is called the monopoly size of G, denoted by mo(G).Ahmed Mohammed NajiandN.D.Soner[7] introduced minimum monopoly energy EMM [G]ofa graph G. In this paper we are introducing the minimum mean monopoly energy, denoted by EM (G), of a graph G and computed minimum monopoly energies of some standard MM graphs. Upper and lower bounds for EM (G)are also established. MM

Keywords

Monopoly Set, Monopoly Size, Minimum Monopoly Matrix, Minimum Mo- nopoly Eigenvalues, Minimum Monopoly Energy and Minimum Mean Monopoly Energy of a graph

ON TOTAL VERTEX IRREGULARITY STRENGTH OF SOME CLASSES OF TADPOLE CHAIN GRAPHS

ON TOTAL VERTEX IRREGULARITY STRENGTH OF SOME CLASSES OF TADPOLE CHAIN GRAPHS

I. Rosyida, D. Indriati

[PDF]

Abstract

A total k-labeling f that assigns V ∪ E into {1, 2, . . . , k} on graph G is named vertex irregular if wtf(u) ̸= wtf(v) for dissimilar vertices u,v in G with the weights wtf (u) = f(u) + ux∈E(G) f(ux). We call the minimum number k utilized in total labeling f as a total vertex irregularity strength of G, symbolized by tvs(G). In this research, we focus on tadpole chain graphs that are chain graphs which con- tain tadpole graphs in their blocks. We investigate tvs of some classes of tadpole chain graphs,. i.e., Tr(4,n) and Tr(5,n) with length r. Some formulas are derived as follows:

Keywords

Vertex irregular total k-labeling, tvs, tadpole graph, chain graph.

OPERATIONS ON TOTALLY WEIGHTED GRAPHS

OPERATIONS ON TOTALLY WEIGHTED GRAPHS

Jicy N.

[PDF]

Abstract

The investigation and study of different operations on graphs leads many in- teresting results in various branches of science and technology. The operations of union, join, corona, Cartesian product and strong product in totally weighted graphs are intro- duced in this article. The types of edges in the resultant graphs are studied and strong connectivity indices of totally weighted graphs through these graph operations are dis- cussed here. Weighted graph operations are relevant, as many complicated networks can be obtained through the operations of basic types of networks.

Keywords

Weighted graph, union, join, Cartesian product, composition, strong connec- tivity index.