**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**18

# Search results for: subgraph

##### 18 Tool for Fast Detection of Java Code Snippets

**Authors:**
Tomáš Bublík,
Miroslav Virius

**Abstract:**

This paper presents general results on the Java source code snippet detection problem. We propose the tool which uses graph and subgraph isomorphism detection. A number of solutions for all of these tasks have been proposed in the literature. However, although that all these solutions are really fast, they compare just the constant static trees. Our solution offers to enter an input sample dynamically with the Scripthon language while preserving an acceptable speed. We used several optimizations to achieve very low number of comparisons during the matching algorithm.

**Keywords:**
AST,
Java,
tree matching,
Scripthon,
source code
recognition

##### 17 Maximum Induced Subgraph of an Augmented Cube

**Authors:**
Meng-Jou Chien,
Jheng-Cheng Chen,
Chang-Hsiung Tsai

**Abstract:**

Let max_{ζG}(*m*) denote the maximum number of edges in a subgraph of graph *G *induced by *m* nodes. The *n*-dimensional augmented cube, denoted as *AQn*, a variation of the hypercube, possesses some properties superior to those of the hypercube. We study the cases when *G* is the augmented cube *AQn*.

**Keywords:**
interconnection network,
augmented cube,
induced subgraph,
bisection width

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

##### 15 The Bipartite Ramsey Numbers b(C2m; C2n)

**Authors:**
Rui Zhang,
Yongqi Sun,
and Yali Wu

**Abstract:**

Given bipartite graphs H1 and H2, the bipartite Ramsey number b(H1;H2) is the smallest integer b such that any subgraph G of the complete bipartite graph Kb,b, either G contains a copy of H1 or its complement relative to Kb,b contains a copy of H2. It is known that b(K2,2;K2,2) = 5, b(K2,3;K2,3) = 9, b(K2,4;K2,4) = 14 and b(K3,3;K3,3) = 17. In this paper we study the case that both H1 and H2 are even cycles, prove that b(C2m;C2n) ≥ m + n - 1 for m = n, and b(C2m;C6) = m + 2 for m ≥ 4.

**Keywords:**
bipartite graph,
Ramsey number,
even cycle

##### 14 Lower Bounds of Some Small Ramsey Numbers

**Authors:**
Decha Samana,
Vites Longani

**Abstract:**

**Keywords:**
Graphs,
lower bound,
Ramsey numbers,
Distance line

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

##### 12 The Giant Component in a Random Subgraph of a Weak Expander

**Authors:**
Yilun Shang

**Abstract:**

In this paper, we investigate the appearance of the giant component in random subgraphs G(p) of a given large finite graph family Gn = (Vn, En) in which each edge is present independently with probability p. We show that if the graph Gn satisfies a weak isoperimetric inequality and has bounded degree, then the probability p under which G(p) has a giant component of linear order with some constant probability is bounded away from zero and one. In addition, we prove the probability of abnormally large order of the giant component decays exponentially. When a contact graph is modeled as Gn, our result is of special interest in the study of the spread of infectious diseases or the identification of community in various social networks.

**Keywords:**
percolation,
Expander,
random graph,
subgraph,
giant component

##### 11 Modeling And Analysis of Simple Open Cycle Gas Turbine Using Graph Networks

**Authors:**
Naresh Yadav,
I.A. Khan,
Sandeep Grover

**Abstract:**

**Keywords:**
Simple open cycle gas turbine,
Graph theoretic approach,
process subgraphs,
gas turbines system modeling,
systemtheory

##### 10 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,
fractional k-factor,
minimum degree,
neighborhood union,
fractional k-deleted graph

##### 9 Decomposition of Graphs into Induced Paths and Cycles

**Authors:**
I. Sahul Hamid,
Abraham V. M.

**Abstract:**

A decomposition of a graph G is a collection ψ of subgraphs H1,H2, . . . , Hr of G such that every edge of G belongs to exactly one Hi. If each Hi is either an induced path or an induced cycle in G, then ψ is called an induced path decomposition of G. The minimum cardinality of an induced path decomposition of G is called the induced path decomposition number of G and is denoted by πi(G). In this paper we initiate a study of this parameter.

**Keywords:**
Path decomposition,
Induced path decomposition,
Induced path decomposition number

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

##### 7 [a, b]-Factors Excluding Some Specified Edges In Graphs

**Authors:**
Sizhong Zhou,
Bingyuan Pu

**Abstract:**

Let G be a graph of order n, and let a, b and m be positive integers with 1 ≤ a<b. An [a, b]-factor of G is deﬁned as a spanning subgraph F of G such that a ≤ dF (x) ≤ b for each x ∈ V (G). In this paper, it is proved that if n ≥ (a+b−1+√(a+b+1)m−2)2−1 b and δ(G) > n + a + b − 2 √bn+ 1, then for any subgraph H of G with m edges, G has an [a, b]-factor F such that E(H)∩ E(F) = ∅. This result is an extension of thatof Egawa [2].

**Keywords:**
graph,
minimum degree,
b]-factor

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

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

**Abstract:**

**Keywords:**
xml,
Graph Structure,
Topological query

##### 5 Maximum Common Substructure Extraction in RNA Secondary Structures Using Clique Detection Approach

**Authors:**
Shih-Yi Chao

**Abstract:**

**Keywords:**
similarity,
subgraph,
Clique detection,
labeled vertices,
RNA secondary
structures

##### 4 A Deterministic Polynomial-time Algorithm for the Clique Problem and the Equality of P and NP Complexity Classes

**Authors:**
Zohreh O. Akbari

**Abstract:**

**Keywords:**
Clique problem,
Deterministic Polynomial-time
Algorithm,
Equality of P and NP Complexity Classes

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

**Authors:**
Frank Emmert Streib

**Abstract:**

**Keywords:**
Graph Partitioning,
unweighted graph,
protein domains

##### 2 N-Sun Decomposition of Complete Graphs and Complete Bipartite Graphs

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

**Abstract:**

**Keywords:**
spanning tree,
Hamilton cycle,
n-sun decomposition,
perfectmatching

##### 1 New Graph Similarity Measurements based on Isomorphic and Nonisomorphic Data Fusion and their Use in the Prediction of the Pharmacological Behavior of Drugs

**Authors:**
Irene Luque Ruiz,
Manuel Urbano Cuadrado,
Miguel Ángel Gómez-Nieto

**Abstract:**

New graph similarity methods have been proposed in this work with the aim to refining the chemical information extracted from molecules matching. For this purpose, data fusion of the isomorphic and nonisomorphic subgraphs into a new similarity measure, the Approximate Similarity, was carried out by several approaches. The application of the proposed method to the development of quantitative structure-activity relationships (QSAR) has provided reliable tools for predicting several pharmacological parameters: binding of steroids to the globulin-corticosteroid receptor, the activity of benzodiazepine receptor compounds, and the blood brain barrier permeability. Acceptable results were obtained for the models presented here.

**Keywords:**
graph similarity,
Nonisomorphic dissimilarity,
Approximate similarity,
Drug activity prediction