Proof of Ding’s Conjecture on Maximal Stable Sets and Maximal Cliques in Planar Graphs

X. Deng et al. proved Chvātal＇s conjecture on maximal stable sets and maximal cliques in graphs. G. Ding made a conjecture to generalize Chvátal＇s conjecture. The purpose of this paper is to prove this conjecture in planar graphs and the complement of planar graphs.

Identification of key genes underlying clinical features of hepatocellular carcinoma based on weighted gene co‑expression network analysis and bioinformatics analysis

Objective: To identify module genes that are closely related to clinical features of hepatocellular carcinoma (HCC) by weighted gene co‑expression network analysis, and to provide a reference for early clinical diagnosis and treatment. Methods: GSE84598 chip data were downloaded from the GEO database, and module genes closely related to the clinical features of HCC were extracted by comprehensive weighted gene co‑expression network analysis. Hub genes were identified through protein interaction network analysis by the maximum clique centrality (MCC) algorithm;Finally, the expression of hub genes was validated by TCGA database and the Kaplan Meier plotter online database was used to evaluate the prognostic relationship between hub genes and HCC patients. Results: By comparing the gene expression data between HCC tissue samples and normal liver tissue samples, a total of 6 262 differentially expressed genes were obtained, of which 2 207 were upregulated and 4 055 were downregulated. Weighted gene co‑expression network analysis was applied to identify 120 genes of key modules. By intersecting with the differentially expressed genes, 115 candidate hub genes were obtained. The results of enrichment analysis showed that the candidate hub genes were closely related to cell mitosis, p53 signaling pathway and so on. Further application of the MCC algorithm to the protein interaction network of 115 candidate hub genes identified five hub genes, namely NUF2, RRM2, UBE2C, CDC20 and MAD2L1. Validation of hub genes by TCGA database revealed that all five hub genes were significantly upregulated in HCC tissues compared to normal liver tissues;Moreover, survival analysis revealed that high expression of hub genes was closely associated with poor prognosis in HCC patients. Conclusions: This study identifies five hub genes by combining multiple databases, which may provide directions for the clinical diagnosis and treatment of HCC.

THE GRAPH INDUCED BY AFFINE M-FLATS OVER FINITE FIELDS II

Let AG(n,F q) be the n-dimensional affine space over F q,where F q is a finite field with q elements.Denote by Γ (m) the graph induced by m-flats of AG(n,F q).For any two adjacent vertices E and F of Γ (m),Γ (m)(E)∩Γ (m)(F) is studied.In particular,sizes of maximal cliques in Γ (m) are determined and it is shown that Γ (m) is not edge-regular when m<n-1.

Most similar maximal clique query on large graphs

This paper studies the most similar maximal clique query(MSMCQ).Given a graph G and a set of nodes Q,MSMCQ is to find the maximal clique of G having the largest similarity with Q.MSMCQ has many real applications including advertising industry,public security,task crowdsourcing and social network,etc.MSMCQ can be studied as a special case of the general set similarity query(SSQ).However,the MCs of G has several specialties from the general sets.Based on the specialties of MCs,we propose a novel index,namely MCIndex.MCIndex outperforms the state-of-the-art SSQ method significantly in terms of the number of candidates and the query time.Specifically,we first construct an inverted indexⅠfor all the MCs of G.Since the MCs in a posting list often have a lot of overlaps,MCIndex selects some pivots to cluster the MCs with a small radius.Given a query Q,we compute the distance from the pivots to Q.The clusters of the pivots assured not answer can be pruned by our distance based pruning rule.Since it is NP-hard to construct a minimum MCIndex,we propose to construct a minimal MCIndex onⅠ(v)with an approximation ratio 1+ln|Ⅰ(v)|.Since the MCs have properties that are inherent of graph structure,we further propose a S Index within each cluster of a MCIndex and a structure based pruning rule.S Index can significantly reduce the number of candidates.Since the sizes of intersections between Q and many MCs need to be computed during the query evaluation,we also propose a binary representation of MCs to improve the efficiency of the intersection size computation.Our extensive experiments confirm the effectiveness and efficiency of our proposed techniques on several real-world datasets.