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.
γ - 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.
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.
We continue research into a well‐studied family of problems that ask whether the vertices of a given graph can be partitioned into sets
A and
B, where
A is an independent set and
B induces a graph ...from some specified graph class
G. We consider the case where
G is the class of
k‐degenerate graphs. This problem is known to be polynomial‐time solvable if
k
=
0 (recognition of bipartite graphs), but
NP‐complete if
k
=
1 (near‐bipartite graphs) even for graphs of maximum degree 4. Yang and Yuan showed that the
k
=
1 case is polynomial‐time solvable for graphs of maximum degree 3. This also follows from a result of Catlin and Lai. We study the general
k
≥
1 case for
n‐vertex graphs of maximum degree
k
+
2. We show how to find
A and
B in
O
(
n
) time for
k
=
1, and in
O
(
n
2
) time for
k
≥
2. Together, these results provide an algorithmic version of a result of Catlin and also provide an algorithmic version of a generalization of Brook's Theorem, proved by Borodin et al. and Matamala. The results also enable us to solve an open problem of Feghali et al. For a given graph
G and positive integer
ℓ, the vertex colouring reconfiguration graph of
G has as its vertex set the set of
ℓ‐colourings of
G and contains an edge between each pair of colourings that differ on exactly on vertex. We complete the complexity classification of the problem of finding a path in the reconfiguration graph between two given
ℓ‐colourings of a given graph of maximum degree
k.
This paper proposes M-channel oversampled filter banks for graph signals. The filter set satisfies the perfect reconstruction condition. A method of designing oversampled graph filter banks is ...presented that allows us to design filters with arbitrary parameters, unlike the conventional critically sampled graph filter banks. The oversampled graph Laplacian matrix is also introduced with a discussion of the entire redundancy of the oversampled graph signal processing system. The practical performance of the proposed filter banks is validated through graph signal denoising experiments.
PDF
