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.
γ - 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.
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.
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.
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.
This Special Issue focuses on recent progress in a new area of mathematical physics and applied analysis, namely, on nonlinear partial differential equations on metric graphs and branched networks. ...Graphs represent a system of edges connected at one or more branching points (vertices). The connection rule determines the graph topology. When the edges can be assigned a length and the wave functions on the edges are defined in metric spaces, the graph is called a metric graph.
Evolution equations on metric graphs have attracted much attention as effective tools for the modeling of particle and wave dynamics in branched structures and networks. Since branched structures and networks appear in different areas of contemporary physics with many applications in electronics, biology, material science, and nanotechnology, the development of effective modeling tools is important for the many practical problems arising in these areas.
The list of important problems includes searches for standing waves, exploring of their properties (e.g., stability and asymptotic behavior), and scattering dynamics. This Special Issue is a representative sample of the works devoted to the solutions of these and other problems.
Random graph matching refers to recovering the underlying vertex correspondence between two random graphs with correlated edges; a prominent example is when the two random graphs are given by ...Erdős-Rényi graphs
G
(
n
,
d
n
)
. This can be viewed as an average-case and noisy version of the graph isomorphism problem. Under this model, the maximum likelihood estimator is equivalent to solving the intractable quadratic assignment problem. This work develops an
O
~
(
n
d
2
+
n
2
)
-time algorithm which perfectly recovers the true vertex correspondence with high probability, provided that the average degree is at least
d
=
Ω
(
log
2
n
)
and the two graphs differ by at most
δ
=
O
(
log
-
2
(
n
)
)
fraction of edges. For dense graphs and sparse graphs, this can be improved to
δ
=
O
(
log
-
2
/
3
(
n
)
)
and
δ
=
O
(
log
-
2
(
d
)
)
respectively, both in polynomial time. The methodology is based on appropriately chosen distance statistics of the degree profiles (empirical distribution of the degrees of neighbors). Before this work, the best known result achieves
δ
=
O
(
1
)
and
n
o
(
1
)
≤
d
≤
n
c
for some constant
c
with an
n
O
(
log
n
)
-time algorithm and
δ
=
O
~
(
(
d
/
n
)
4
)
and
d
=
Ω
~
(
n
4
/
5
)
with a polynomial-time algorithm.
PDF
