**Commenced**in January 2007

**Frequency:**Monthly

**Edition:**International

**Paper Count:**16

# Search results for: subgraph

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

##### 15 Identifying Network Subgraph-Associated Essential Genes in Molecular Networks

**Authors:**
Efendi Zaenudin,
Chien-Hung Huang,
Ka-Lok Ng

**Abstract:**

Essential genes play an important role in the survival of an organism. It has been shown that cancer-associated essential genes are genes necessary for cancer cell proliferation, where these genes are potential therapeutic targets. Also, it was demonstrated that mutations of the cancer-associated essential genes give rise to the resistance of immunotherapy for patients with tumors. In the present study, we focus on studying the biological effects of the essential genes from a network perspective. We hypothesize that one can analyze a biological molecular network by decomposing it into both three-node and four-node digraphs (subgraphs). These network subgraphs encode the regulatory interaction information among the network’s genetic elements. In this study, the frequency of occurrence of the subgraph-associated essential genes in a molecular network was quantified by using the statistical parameter, odds ratio. Biological effects of subgraph-associated essential genes are discussed. In summary, the subgraph approach provides a systematic method for analyzing molecular networks and it can capture useful biological information for biomedical research.

**Keywords:**
Biological molecular networks,
essential genes,
graph theory,
network subgraphs.

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

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

**Abstract:**

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

##### 13 [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,
[a,
b]-factor.

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

**Authors:**
Decha Samana,
Vites Longani

**Abstract:**

**Keywords:**
Lower bound,
Ramsey numbers,
Graphs,
Distance line.

##### 11 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:**
subgraph,
expander,
random graph,
giant component,
percolation.

##### 10 Cirrhosis Mortality Prediction as Classification Using Frequent Subgraph Mining

**Authors:**
Abdolghani Ebrahimi,
Diego Klabjan,
Chenxi Ge,
Daniela Ladner,
Parker Stride

**Abstract:**

In this work, we use machine learning and data analysis techniques to predict the one-year mortality of cirrhotic patients. Data from 2,322 patients with liver cirrhosis are collected at a single medical center. Different machine learning models are applied to predict one-year mortality. A comprehensive feature space including demographic information, comorbidity, clinical procedure and laboratory tests is being analyzed. A temporal pattern mining technic called Frequent Subgraph Mining (FSM) is being used. Model for End-stage liver disease (MELD) prediction of mortality is used as a comparator. All of our models statistically significantly outperform the MELD-score model and show an average 10% improvement of the area under the curve (AUC). The FSM technic itself does not improve the model significantly, but FSM, together with a machine learning technique called an ensemble, further improves the model performance. With the abundance of data available in healthcare through electronic health records (EHR), existing predictive models can be refined to identify and treat patients at risk for higher mortality. However, due to the sparsity of the temporal information needed by FSM, the FSM model does not yield significant improvements. Our work applies modern machine learning algorithms and data analysis methods on predicting one-year mortality of cirrhotic patients and builds a model that predicts one-year mortality significantly more accurate than the MELD score. We have also tested the potential of FSM and provided a new perspective of the importance of clinical features.

**Keywords:**
machine learning,
liver cirrhosis,
subgraph mining,
supervised learning

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

**Authors:**
Shih-Yi Chao

**Abstract:**

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

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

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

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

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

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

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

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

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

**Abstract:**

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

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