**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**1267

# Search results for: Derived graph

##### 1267 Metric Dimension on Line Graph of Honeycomb Networks

**Authors:**
M. Hussain,
Aqsa Farooq

**Abstract:**

**Keywords:**
Resolving set,
metric dimension,
honeycomb network,
line graph.

##### 1266 Nullity of t-Tupple Graphs

**Authors:**
Khidir R. Sharaf,
Didar A. Ali

**Abstract:**

The nullity η(G) of a graph is the occurrence of zero as an eigenvalue in its spectra. A zero-sum weighting of a graph G is real valued function, say f from vertices of G to the set of real numbers, provided that for each vertex of G the summation of the weights f(w) over all neighborhood w of v is zero for each v in G.A high zero-sum weighting of G is one that uses maximum number of non-zero independent variables. If G is graph with an end vertex, and if H is an induced subgraph of G obtained by deleting this vertex together with the vertex adjacent to it, then, η(G)= η(H). In this paper, a high zero-sum weighting technique and the endvertex procedure are applied to evaluate the nullity of t-tupple and generalized t-tupple graphs are derived and determined for some special types of graphs,

Also, we introduce and prove some important results about the t-tupple coalescence, Cartesian and Kronecker products of nut graphs.

**Keywords:**
Graph theory,
Graph spectra,
Nullity of graphs.

##### 1265 On Chvátal’s Conjecture for the Hamiltonicity of 1-Tough Graphs and Their Complements

**Authors:**
Shin-Shin Kao,
Yuan-Kang Shih,
Hsun Su

**Abstract:**

In this paper, we show that the conjecture of Chv tal, which states that any 1-tough graph is either a Hamiltonian graph or its complement contains a specific graph denoted by F, does not hold in general. More precisely, it is true only for graphs with six or seven vertices, and is false for graphs with eight or more vertices. A theorem is derived as a correction for the conjecture.

**Keywords:**
Complement,
degree sum,
Hamiltonian,
tough.

##### 1264 Efficient Filtering of Graph Based Data Using Graph Partitioning

**Authors:**
Nileshkumar Vaishnav,
Aditya Tatu

**Abstract:**

**Keywords:**
Graph signal processing,
graph partitioning,
inverse
filtering on graphs,
algebraic signal processing.

##### 1263 Using Spectral Vectors and M-Tree for Graph Clustering and Searching in Graph Databases of Protein Structures

**Authors:**
Do Phuc,
Nguyen Thi Kim Phung

**Abstract:**

**Keywords:**
Eigenvalues,
m-tree,
graph database,
protein
structure,
spectra graph theory.

##### 1262 A Neighborhood Condition for Fractional k-deleted Graphs

**Authors:**
Sizhong Zhou,
Hongxia Liu

**Abstract:**

Abstract–Let k ≥ 3 be an integer, and let G be a graph of order n with n ≥ 9k +3- 42(k - 1)2 + 2. Then a spanning subgraph F of G is called a k-factor if dF (x) = k for each x ∈ V (G). A fractional k-factor is a way of assigning weights to the edges of a graph G (with all weights between 0 and 1) such that for each vertex the sum of the weights of the edges incident with that vertex is k. A graph G is a fractional k-deleted graph if there exists a fractional k-factor after deleting any edge of G. In this paper, it is proved that G is a fractional k-deleted graph if G satisfies δ(G) ≥ k + 1 and |NG(x) ∪ NG(y)| ≥ 1 2 (n + k - 2) for each pair of nonadjacent vertices x, y of G.

**Keywords:**
Graph,
minimum degree,
neighborhood union,
fractional k-factor,
fractional k-deleted graph.

##### 1261 The Extremal Graph with the Largest Merrifield-Simmons Index of (n, n + 2)-graphs

**Authors:**
M. S. Haghighat,
A. Dolati,
M. Tabari,
E. Mohseni

**Abstract:**

The Merrifield-Simmons index of a graph G is defined as the total number of its independent sets. A (n, n + 2)-graph is a connected simple graph with n vertices and n + 2 edges. In this paper we characterize the (n, n+2)-graph with the largest Merrifield- Simmons index. We show that its Merrifield-Simmons index i.e. the upper bound of the Merrifield-Simmons index of the (n, n+2)-graphs is 9 × 2n-5 +1 for n ≥ 5.

**Keywords:**
Merrifield-Simmons index,
(n,
n+2)-graph.

##### 1260 N-Sun Decomposition of Complete, Complete Bipartite and Some Harary Graphs

**Authors:**
R. Anitha,
R. S. Lekshmi

**Abstract:**

**Keywords:**
Decomposition,
Hamilton cycle,
n-sun graph,
perfect matching,
spanning tree.

##### 1259 The Diameter of an Interval Graph is Twice of its Radius

**Authors:**
Tarasankar Pramanik,
Sukumar Mondal,
Madhumangal Pal

**Abstract:**

In an interval graph G = (V,E) the distance between two vertices u, v is de£ned as the smallest number of edges in a path joining u and v. The eccentricity of a vertex v is the maximum among distances from all other vertices of V . The diameter (δ) and radius (ρ) of the graph G is respectively the maximum and minimum among all the eccentricities of G. The center of the graph G is the set C(G) of vertices with eccentricity ρ. In this context our aim is to establish the relation ρ = δ 2 for an interval graph and to determine the center of it.

**Keywords:**
Interval graph,
interval tree,
radius,
center.

##### 1258 Completion Number of a Graph

**Authors:**
Sudhakar G

**Abstract:**

In this paper a new concept of partial complement of a graph G is introduced and using the same a new graph parameter, called completion number of a graph G, denoted by c(G) is defined. Some basic properties of graph parameter, completion number, are studied and upperbounds for completion number of classes of graphs are obtained , the paper includes the characterization also.

**Keywords:**
Completion Number,
Maximum Independent subset,
Partial complements,
Partial self complementary

##### 1257 On Fractional (k,m)-Deleted Graphs with Constrains Conditions

**Authors:**
Sizhong Zhou,
Hongxia Liu

**Abstract:**

Let G be a graph of order n, and let k 2 and m 0 be two integers. Let h : E(G) [0, 1] be a function. If e∋x h(e) = k holds for each x V (G), then we call G[Fh] a fractional k-factor of G with indicator function h where Fh = {e E(G) : h(e) > 0}. A graph G is called a fractional (k,m)-deleted graph if there exists a fractional k-factor G[Fh] of G with indicator function h such that h(e) = 0 for any e E(H), where H is any subgraph of G with m edges. In this paper, it is proved that G is a fractional (k,m)-deleted graph if (G) k + m + m k+1 , n 4k2 + 2k − 6 + (4k 2 +6k−2)m−2 k−1 and max{dG(x), dG(y)} n 2 for any vertices x and y of G with dG(x, y) = 2. Furthermore, it is shown that the result in this paper is best possible in some sense.

**Keywords:**
Graph,
degree condition,
fractional k-factor,
fractional (k,
m)-deleted graph.

##### 1256 Comparison of Full Graph Methods of Switched Circuits Solution

**Authors:**
Zdeňka Dostálová,
David Matoušek,
Bohumil Brtnik

**Abstract:**

**Keywords:**
Switched capacitors of two phases,
switched
currents of two phases,
transformation graph,
two-graph,
Mason's
formula,
voltage transfer,
summary graph.

##### 1255 Speedup Breadth-First Search by Graph Ordering

**Abstract:**

Breadth-First Search (BFS) is a core graph algorithm that is widely used for graph analysis. As it is frequently used in many graph applications, improving the BFS performance is essential. In this paper, we present a graph ordering method that could reorder the graph nodes to achieve better data locality, thus, improving the BFS performance. Our method is based on an observation that the sibling relationships will dominate the cache access pattern during the BFS traversal. Therefore, we propose a frequency-based model to construct the graph order. First, we optimize the graph order according to the nodes’ visit frequency. Nodes with high visit frequency will be processed in priority. Second, we try to maximize the child nodes’ overlap layer by layer. As it is proved to be NP-hard, we propose a heuristic method that could greatly reduce the preprocessing overheads.We conduct extensive experiments on 16 real-world datasets. The result shows that our method could achieve comparable performance with the state-of-the-art methods while the graph ordering overheads are only about 1/15.

**Keywords:**
Breadth-first search,
BFS,
graph ordering,
graph algorithm.

##### 1254 On Detour Spectra of Some Graphs

**Authors:**
S.K.Ayyaswamy,
S.Balachandran

**Abstract:**

**Keywords:**
Detour eigenvalue (of a graph),
detour spectrum(of a graph),
detour energy(of a graph),
detour - equienergetic graphs.

##### 1253 Analysis of Electrical Networks Using Phasors: A Bond Graph Approach

**Authors:**
Israel Núñez-Hernández,
Peter C. Breedveld,
Paul B. T. Weustink,
Gilberto Gonzalez-A

**Abstract:**

This paper proposes a phasor representation of electrical networks by using bond graph methodology. A so-called phasor bond graph is built up by means of two-dimensional bonds, which represent the complex plane. Impedances or admittances are used instead of the standard bond graph elements. A procedure to obtain the steady-state values from a phasor bond graph model is presented. Besides the presentation of a phasor bond graph library in SIDOPS code, also an application example is discussed.

**Keywords:**
Bond graphs,
phasor theory,
steady-state,
complex
power,
electrical networks.

##### 1252 Bounds on the Second Stage Spectral Radius of Graphs

**Authors:**
S.K.Ayyaswamy,
S.Balachandran,
K.Kannan

**Abstract:**

Let G be a graph of order n. The second stage adjacency matrix of G is the symmetric n × n matrix for which the ijth entry is 1 if the vertices vi and vj are of distance two; otherwise 0. The sum of the absolute values of this second stage adjacency matrix is called the second stage energy of G. In this paper we investigate a few properties and determine some upper bounds for the largest eigenvalue.

**Keywords:**
Second stage spectral radius,
Irreducible matrix,
Derived graph

##### 1251 Topological Queries on Graph-structured XML Data: Models and Implementations

**Authors:**
Hongzhi Wang,
Jianzhong Li,
Jizhou Luo

**Abstract:**

**Keywords:**
XML,
Graph Structure,
Topological query.

##### 1250 An Efficient Graph Query Algorithm Based on Important Vertices and Decision Features

**Authors:**
Xiantong Li,
Jianzhong Li

**Abstract:**

**Keywords:**
Decision Feature,
Frequent Feature,
Graph Dataset,
Graph Query

##### 1249 Notes on Fractional k-Covered Graphs

**Authors:**
Sizhong Zhou,
Yang Xu

**Abstract:**

**Keywords:**
graph,
binding number,
fractional k-factor,
fractional k-covered graph.

##### 1248 Syntactic Recognition of Distorted Patterns

**Authors:**
Marek Skomorowski

**Abstract:**

**Keywords:**
Syntactic pattern recognition,
Distorted patterns,
Random graphs,
Graph grammars.

##### 1247 Automatic Fingerprint Classification Using Graph Theory

**Authors:**
Mana Tarjoman,
Shaghayegh Zarei

**Abstract:**

Using efficient classification methods is necessary for automatic fingerprint recognition system. This paper introduces a new structural approach to fingerprint classification by using the directional image of fingerprints to increase the number of subclasses. In this method, the directional image of fingerprints is segmented into regions consisting of pixels with the same direction. Afterwards the relational graph to the segmented image is constructed and according to it, the super graph including prominent information of this graph is formed. Ultimately we apply a matching technique to compare obtained graph with the model graphs in order to classify fingerprints by using cost function. Increasing the number of subclasses with acceptable accuracy in classification and faster processing in fingerprints recognition, makes this system superior.

**Keywords:**
Classification,
Directional image,
Fingerprint,
Graph,
Super graph.

##### 1246 Graphs with Metric Dimension Two-A Characterization

**Authors:**
Sudhakara G,
Hemanth Kumar A.R

**Abstract:**

In this paper, we define distance partition of vertex set of a graph G with reference to a vertex in it and with the help of the same, a graph with metric dimension two (i.e. β (G) = 2 ) is characterized. In the process, we develop a polynomial time algorithm that verifies if the metric dimension of a given graph G is two. The same algorithm explores all metric bases of graph G whenever β (G) = 2 . We also find a bound for cardinality of any distance partite set with reference to a given vertex, when ever β (G) = 2 . Also, in a graph G with β (G) = 2 , a bound for cardinality of any distance partite set as well as a bound for number of vertices in any sub graph H of G is obtained in terms of diam H .

**Keywords:**
Metric basis,
Distance partition,
Metric dimension.

##### 1245 Topological Properties of an Exponential Random Geometric Graph Process

**Authors:**
Yilun Shang

**Abstract:**

**Keywords:**
random geometric graph,
autoregressive process,
degree,
connectivity,
Markovian,
wireless network.

##### 1244 Image Segmentation Using Suprathreshold Stochastic Resonance

**Authors:**
Rajib Kumar Jha,
P.K.Biswas,
B.N.Chatterji

**Abstract:**

In this paper a new concept of partial complement of a graph G is introduced and using the same a new graph parameter, called completion number of a graph G, denoted by c(G) is defined. Some basic properties of graph parameter, completion number, are studied and upperbounds for completion number of classes of graphs are obtained , the paper includes the characterization also.

**Keywords:**
Completion Number,
Maximum Independent subset,
Partial complements,
Partial self complementary.

##### 1243 Analysis of a Singular Perturbed Synchronous Generator with a Bond Graph Approach

**Authors:**
Gilberto Gonzalez-A,
Noe Barrera-G

**Abstract:**

**Keywords:**
Bond graph modelling,
synchronous generator,
singular perturbations

##### 1242 Connected Vertex Cover in 2-Connected Planar Graph with Maximum Degree 4 is NP-complete

**Authors:**
Priyadarsini P. L. K,
Hemalatha T.

**Abstract:**

**Keywords:**
NP-complete,
2-Connected planar graph,
block,
cut vertex

##### 1241 Protein Graph Partitioning by Mutually Maximization of cycle-distributions

**Authors:**
Frank Emmert Streib

**Abstract:**

**Keywords:**
Graph partitioning,
unweighted graph,
protein domains.

##### 1240 Eccentric Connectivity Index, First and Second Zagreb Indices of Corona Graph

**Authors:**
A. Kulandai Therese

**Abstract:**

The eccentric connectivity index based on degree and eccentricity of the vertices of a graph is a widely used graph invariant in mathematics. In this paper, we present the explicit eccentric connectivity index, first and second Zagreb indices for a Corona graph and sub divisionrelated corona graphs.

**Keywords:**
Corona graph,
Degree,
Eccentricity,
Eccentric
Connectivity Index,
First Zagreb index,
Second Zagreb index and
Subdivision graphs.

##### 1239 Analysis of a Hydroelectric Plant connected to Electrical Power System in the Physical Domain

**Authors:**
Gilberto Gonzalez-A,
Octavio Barriga

**Abstract:**

**Keywords:**
Bond graph,
hydraulic plant,
steady state.

##### 1238 Image Segmentation Based on Graph Theoretical Approach to Improve the Quality of Image Segmentation

**Authors:**
Deepthi Narayan,
Srikanta Murthy K.,
G. Hemantha Kumar

**Abstract:**

**Keywords:**
Graph based image segmentation,
threshold,
Weighted Euclidean distance.