γ - Uniquely colorable graphs Yamuna, M; Elakkiya, A
IOP conference series. Materials Science and Engineering,
11/2017, Volume:
263, Issue:
4
Journal Article
Peer reviewed
Open access
A graph G = ( V, E ) is uniquely colorable if the chromatic number χ ( G ) = n and every n - coloring of G induces the same partition of V. In this paper, we introduce a new kind of graph called γ - ...uniquely colorable graphs. We obtain a necessary and sufficient condition for a graph to be γ - uniquely colorable graphs. We provide a constructive characterization of γ - uniquely colorable trees.
Non - domination subdivision stable graphs Yamuna, M; Elakkiya, A
IOP conference series. Materials Science and Engineering,
11/2017, Volume:
263, Issue:
4
Journal Article
Peer reviewed
Open access
Subdividing an edge in the graph may increase the domination number or remains the same. In this paper, we introduce a new kind of graph called non - domination subdivision stable graph (NDSS). We ...obtain a necessary and sufficient condition for a graph to be NDSS. We provide a constructive characterization of NDSS trees and a MATLAB program for identifying NDSS graphs.
Degree sequence in message transfer Yamuna, M
IOP conference series. Materials Science and Engineering,
11/2017, Volume:
263, Issue:
4
Journal Article
Peer reviewed
Open access
Message encryption is always an issue in current communication scenario. Methods are being devised using various domains. Graphs satisfy numerous unique properties which can be used for message ...transfer. In this paper, I propose a message encryption method based on degree sequence of graphs.
Edge Hubtic Number in Graphs Khalaf, Shadi Ibrahim; Mathad, Veena; Mahde, Sultan Senan
International journal of mathematical combinatorics,
09/2018, Volume:
3
Journal Article
Open access
The maximum order of partition of the edge set E(G) into edge hub sets is called edge hubtic number of G and denoted by Ξe(G). In this paper, we determine the edge hubtic number of some standard ...graphs. Also we obtain bounds for Ξe(G). In addition we characterize the class of all (p,q) graphs for which Ξe(G) = q.
Recently, several works by a number of authors have provided characterizations of integral undirected Cayley graphs over generalized dihedral groups and generalized dicyclic groups. We generalize and ...unify these results in two different ways. Firstly, we work over arbitrary non-abelian finite groups admitting an abelian subgroup of index 2. Secondly, our main result actually characterizes integral mixed Cayley graphs over such finite groups, in the spirit of a very recent result of Kadyan–Bhattarcharjya in the abelian case.
We consider the vertex proper coloring problem for highly restricted instances of geometric intersection graphs of line segments embedded in the plane. Provided a graph in the class UNIT-PURE-
k
...-DIR, corresponding to intersection graphs of unit length segments lying in at most
k
directions with all parallel segments disjoint, and provided explicit coordinates for segments whose intersections induce the graph, we show for
k
=
4
that it is
NP
-complete to decide if a proper 3-coloring exists, and moreover,
#
P
-complete under many-one counting reductions to determine the number of such colorings. In addition, under the more relaxed constraint that segments have at most two distinct lengths, we show these same hardness results hold for finding and counting proper
k
-
1
-colorings for every
k
≥
5
. More generally, we establish that the problem of proper 3-coloring an arbitrary graph with
m
edges can be reduced in
O
m
2
time to the problem of proper 3-coloring a UNIT-PURE-4-DIR graph. This can then be shown to imply that no
2
o
n
time algorithm can exist for proper 3-coloring PURE-4-DIR graphs under the Exponential Time Hypothesis (ETH), and by a slightly more elaborate construction, that no
2
o
n
time algorithm can exist for counting the such colorings under the Counting Exponential Time Hypothesis (#ETH). Finally, we prove an
NP
-hardness result for the optimization problem of finding a maximum order proper 3-colorable induced subgraph of a UNIT-PURE-4-DIR graph.
The resistance distance between any two vertices of a graph G is defined as the network effective resistance between them if each edge of G is replaced by a unit resistor. The Kirchhoff index K(G) is ...the sum of the resistance distances between all the pairs of vertices in G. A bicyclic graph is a connected graph whose number of edges is exactly one more than its number of vertices. In this paper, we completely characterize the bicyclic graphs of order n≥4 with minimal Kirchhoff index and determine bounds on the Kirchhoff index of bicyclic graphs. This improves and extends some earlier results.
For natural numbers k<n we study the graphs Tn,k:=Kk∨Kn−k‾. For k=1, Tn,1 is the star Sn−1. For k>1 we refer to Tn,k as a graph of pyramids. We prove that the graphs of pyramids are determined by ...their spectrum, and that a star Sn is determined by its spectrum iff n is prime. We also show that the graphs Tn,k are completely positive iff k≤2.
PDF
