**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**1311

# Search results for: Interaction graph

##### 1311 Intention Recognition using a Graph Representation

**Authors:**
So-Jeong Youn,
Kyung-Whan Oh

**Abstract:**

**Keywords:**
Intention recognition,
intention,
graph,
HCI.

##### 1310 Detecting Community Structure in Amino Acid Interaction Networks

**Authors:**
Omar GACI,
Stefan BALEV,
Antoine DUTOT

**Abstract:**

In this paper we introduce the notion of protein interaction network. This is a graph whose vertices are the protein-s amino acids and whose edges are the interactions between them. Using a graph theory approach, we observe that according to their structural roles, the nodes interact differently. By leading a community structure detection, we confirm this specific behavior and describe thecommunities composition to finally propose a new approach to fold a protein interaction network.

**Keywords:**
interaction network,
protein structure,
community structure detection.

##### 1309 A General Model for Amino Acid Interaction Networks

**Authors:**
Omar Gaci,
Stefan Balev

**Abstract:**

**Keywords:**
interaction network,
protein structure,
small-world network.

##### 1308 Selecting Negative Examples for Protein-Protein Interaction

**Authors:**
Mohammad Shoyaib,
M. Abdullah-Al-Wadud,
Oksam Chae

**Abstract:**

**Keywords:**
Interaction graph,
Negative training data,
Protein-Protein interaction,
Support vector machine.

##### 1307 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.

##### 1306 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.

##### 1305 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.

##### 1304 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.

##### 1303 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.

##### 1302 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.

##### 1301 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

##### 1300 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.

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

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

**Abstract:**

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

##### 1298 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.

##### 1297 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.

##### 1296 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.

##### 1295 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.

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

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

**Abstract:**

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

##### 1293 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

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

**Authors:**
Sizhong Zhou,
Yang Xu

**Abstract:**

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

##### 1291 Improved Algorithms for Construction of Interface Agent Interaction Model

**Authors:**
Huynh Quyet Thang,
Le Hai Quan

**Abstract:**

**Keywords:**
interface agent,
interaction model,
user model.

##### 1290 Syntactic Recognition of Distorted Patterns

**Authors:**
Marek Skomorowski

**Abstract:**

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

##### 1289 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.

##### 1288 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.

##### 1287 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.

##### 1286 Bond Graph Modeling of Inter-Actuator Interactions in a Multi-Cylinder Hydraulic System

**Authors:**
Mutuku Muvengei,
John Kihiu

**Abstract:**

**Keywords:**
Bond graphs,
Inter-actuator interactions,
Valvecontrolledhydraulic cylinder.

##### 1285 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

##### 1284 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

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

**Authors:**
Frank Emmert Streib

**Abstract:**

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

##### 1282 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.