Abstract. We prove that a signed graph admits a nowhere-zero 8-flow, provided that it is flow-admissible and the underlying graph admits a nowhere-zero 4-flow. When combined with the 4-color theorem, this implies that every flow-admissible bridgeless planar signed graph admits a nowhere-zero 8-flow. Our result improves and generalizes previous results of Li et al. [ European J. Combin., 108 (2023), 103627], which state that every flow-admissible signed 3-edge-colorable cubic graph admits a nowhere-zero 10-flow and that every flow-admissible signed Hamiltonian graph admits a nowhere-zero 8-flow.

Abstract. It is conjectured that every bridgeless graph [Formula: see text] has a family [Formula: see text] of even subgraphs (cycles) such that each edge of [Formula: see text] is contained in precisely two members of [Formula: see text] (CDC), and a stronger conjecture says that every bridgeless graph has a 5-even subgraph double cover (5-CDC). Both the CDC and the 5-CDC conjectures are confirmed for cubic graphs with oddness at most 4. In this paper, we first introduce a new approach related to nowhere-zero 4-flows to attack these two conjectures, and then apply it together with Catlin reduction to present a sufficient condition for a superposition to have a 5-CDC. As an application of those results, the 5-CDC conjecture is verified for several families of snarks.

This paper studies the fundamental relations among integer flows, modulo orientations, integer-valued and real-valued circular flows, and monotonicity of flows in signed graphs. A (signed) graph is modulo-$(2p+1)$-orientable if it has an orientation such that the indegree is congruent to the outdegree modulo $2p+1$ at each vertex. An integer-valued $\frac{2p+1}{p}$-flow is a flow taking integer values in $\{\pm p, \pm (p+1)\}$. Extending a fundamental result of Jaeger to signed graphs, we show that a bridgeless signed graph is modulo-$(2p+1)$-orientable if and only if it admits an integer-valued $\frac{2p+1}{p}$-flow. It was conjectured by Raspaud and Zhu that, for any signed graph, the admission of a circular $r$-flow implies the admission of an integer-valued $\lceil r \rceil$-flow. Although this conjecture has been disproved in general, it is confirmed in this paper for bridgeless signed graphs if $r=\frac{2p+1}{p}$ and $p \geq 3$.

Many basic properties in Tutte's flow theory for unsigned graphs do not have their counterparts for signed graphs. However, signed graphs without long barbells in many ways behave like unsigned graphs from the point view of flows. In this paper, we study whether some basic properties in Tutte's flow theory remain valid for this family of signed graphs. Specifically let $(G,\sigma)$ be a flow-admissible signed graph without long barbells. We show that it admits a nowhere-zero 6-flow and that it admits a nowhere-zero modulo $k$-flow if and only if it admits a nowhere-zero integer $k$-flow for each integer $k\geq 3$ and $k \not = 4$. We also show that each nowhere-zero positive integer $k$-flow of $(G,\sigma)$ can be expressed as the sum of some 2-flows. For general graphs, we show that every nowhere-zero $\frac{p}{q}$-flow can be normalized in such a way, that each flow value is a multiple of $\frac{1}{2q}$. As a consequence we prove the equality of the integer flow number and the ceiling of the circular flow number for flow-admissible signed graphs without long barbells.

Converting modulo flows into integer-valued flows is one of the most critical steps in the study of integer flows. Tutte and Jaeger's pioneering work shows the equivalence of modulo flows and integer-valued flows for ordinary graphs. However, such equivalence no longer holds for signed graphs. This motivates us to study how to convert modulo flows into integer-valued flows for signed graphs. In this paper, we generalize some early results by Xu and Zhang [ Discrete Math., 299 (2005), pp. 335--343], Schubert and Steffen [ European J. Combin., 48 (2015), pp. 34--47], and Zhu [ J. Combin. Theory Ser. B, 112 (2015), pp. 93--103] and show that, for signed graphs, every modulo $(2+\frac{1}{p})$-flow with $p \in {\mathbb Z}^+ \cup \{\infty\}$ can be converted/extended into an integer-valued flow.

Signed networks with both positive and negative links have gained considerable attention over the past several years. Community detection is among the main challenges for signed network analysis. It aims to find mutually antagonistic groups such that entities within the same group have as many positive relationships as possible and entities between different groups have as many negative relationships as possible. Most existing algorithms for community detection in signed networks aim to provide a hard partition of the network where any node should belong to a single community. However, overlapping communities, where a node is allowed to belong to multiple communities, widely exist in many real-world networks. Another disadvantage of some existing algorithms is that the number of final clusters k should be an input of the clustering process. It may however be the case that we do not know k in advance. In this paper, to offer improvements to existing algorithms, we propose a new clustering method for signed networks, the Signed Quasi-clique Merger (SQCM) algorithm. This algorithm detects the meaningful clusters (i.e. subgraphs with high friendly density) from the networks directly, where the friendly density of a subgraph [Formula: see text] is defined as [Formula: see text]. We construct a hierarchically nested system to illustrate their inclusion relationships. The output of SQCM is a smaller hierarchical tree, which clearly highlights meaningful clusters. During the clustering process, we do not need to know the number of final clusters k in advance; the algorithm is able to detect it on its own. Another important feature of SQCM is overlapping clustering or multi-membership. Its effectiveness is demonstrated through rigorous experiments involving both benchmark and randomly generated signed networks.

A vector ${S}^d$-flow is a flow whose flow values are vectors in $S^d$, where $S^d$ is the set of all unit vectors in $\mathbb{R}^{d+1}$. Jain [Open Problem Garden, http://www.openproblemgarden.org/op/unit_vector_flows (2007)] and Thomassen [J. Combin. Theory Ser. B., 108 (2014), pp. 81--91] proved that a graph has a vector $S^1$-flow if it has a nowhere-zero integer 3-flow. Thomassen [J. Combin. Theory Ser. B., 108 (2014), pp. 81--91] pointed out that a graph admitting a vector $S^1$-flow may not necessarily admit a nowhere-zero integer 3-flow and presented a family of examples showing that the converse is not true. The rank of a vector $S^1$-flow $( D,\bm {f} )$ is defined as the rank of linear space generated by all balanced vectors ${\bm{\epsilon}}(v)=(\epsilon_1(v), \epsilon_2(v), \ldots, \epsilon_b(v))$ for all $v \in V(G)$, where $\epsilon_i(v)$ is the difference between the number of outgoing edges with flow value ${\bm \alpha}_i$ from $v$ and the number of ingoing edges with the same flow value to $v$. In this paper, we prove that $G$ admits a nowhere-zero integer 3-flow if $G$ admits a vector $S^{1}$-flow with rank at most two. This result is sharp since there are examples that admit vector $S^1$-flows with rank at least 3, but no nowhere-zero integer 3-flows.

Tutte observed that every nowhere-zero $k$-flow on a plane graph gives rise to a $k$-vertex-coloring of its dual, and vice versa. Thus nowhere-zero integer flow and graph coloring can be viewed as dual concepts. Jaeger further shows that if a graph $G$ has a face-$k$-colorable 2-cell embedding in some orientable surface, then it has a nowhere-zero $k$-flow. However, if the surface is nonorientable, then a face-$k$-coloring corresponds to a nowhere-zero $k$-flow in a signed graph arising from $G$. Graphs embedded in orientable surfaces are therefore a special case that the corresponding signs are all positive. In this paper, we prove that if an 8-edge-connected signed graph admits a nowhere-zero integer flow, then it has a nowhere-zero 3-flow. Our result extends Thomassen's 3-flow theorem on 8-edge-connected graphs to the family of all 8-edge-connected signed graphs. And it also improves Zhu's 3-flow theorem on 11-edge-connected signed graphs.

In data mining, hierarchical clustering is a method of cluster analysis which seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types: agglomerative and divisive. In this paper we shall introduce a new optimal selection method based on the well-known Max-Flow Min-Cut theorem, which also works for the hierarchically structure with overlapping. A novel dynamic algorithm was presented for the special structure without overlapping.

BACKGROUND: Using gene co-expression analysis, researchers were able to predict clusters of genes with consistent functions that are relevant to cancer development and prognosis. We applied a weighted gene co-expression network (WGCN) analysis algorithm on glioblastoma multiforme (GBM) data obtained from the TCGA project and predicted a set of gene co-expression networks which are related to GBM prognosis. METHODS: We modified the Quasi-Clique Merger algorithm (QCM algorithm) into edge-covering Quasi-Clique Merger algorithm (eQCM) for mining weighted sub-network in WGCN. Each sub-network is considered a set of features to separate patients into two groups using K-means algorithm. Survival times of the two groups are compared using log-rank test and Kaplan-Meier curves. Simulations using random sets of genes are carried out to determine the thresholds for log-rank test p-values for network selection. Sub-networks with p-values less than their corresponding thresholds were further merged into clusters based on overlap ratios (>50%). The functions for each cluster are analyzed using gene ontology enrichment analysis. RESULTS: Using the eQCM algorithm, we identified 8,124 sub-networks in the WGCN, out of which 170 sub-networks show p-values less than their corresponding thresholds. They were then merged into 16 clusters. CONCLUSIONS: We identified 16 gene clusters associated with GBM prognosis using the eQCM algorithm. Our results not only confirmed previous findings including the importance of cell cycle and immune response in GBM, but also suggested important epigenetic events in GBM development and prognosis.

The complex network of relationships between countries provides an abundance of data from which intelligence analysts must synthesize useful interpretations that effectively inform foreign policy and security decision making. In this work, a network of foreign policy event interactions is developed and then used to describe the state of the international system by estimating the behavioral distances from all relevant actors to the US. Using a graph theoretic approach, we develop a tool for estimating behavioral distances through direct network links when behavior is present, and indirect network paths when direct behavior is unobserved. The international system is examined in temporal aggregations of 60 and 30 days prior to and following the 1991 Gulf War and the 2003 invasion of Iraq. Both periods see distancing from the US as the wars approach, and a partial return to the prior state by 60 days after the initiation of conflict. The overall position of the US and the response of other nations towards the US indicates that the systemic leadership role of the US is diminished in behavioral relationships with a moderate number of actors.

Extremist political movements have proliferated on the web in recent years due to the advent of minimal publication costs coupled with near universal access, resulting in what appears to be an abundance of groups that hover on the fringe of many socially divisive issues. Whether white-supremacist, neo- Nazi, anti-abortion, black separatist, radical Christian, animal rights, or violent environmentalists, all have found a home (and voice) on the Web. These groups form social networks whose ties are predicated primarily on shared political goals. Little is known about these groups, their interconnections, their animosities, and most importantly, their growth and development and studies such as the Dark Web Project, while considering domestic extremists, have focused primarily on international terrorist groups. Yet here in the US, there has been a complex social dynamic unfolding as well. While left-wing radicalism declined throughout the 80s and 90s, right wing hate groups began to flourish. Today, the web offers a place for any brand of extremism, but little is understood about their current growth and development. While there is much to gain from in-depth studies of the content provided by these sites, there is also a surprising amount of information contained in their online network structure as manifested in links between and among these web sites. Our research follows the idea that much can be known about you by the company you keep. In this paper, we propose an approach to measure the intrinsic relationships (i.e., similarities) of a set of extremist web pages. In this model, the web presence of a group is thought of as a node in a social network and the links between these pages are the ties between groups. This approach takes the bi-directional hyperlink structure of web pages and, based on similarity scores, applies an effective multi-membership clustering algorithm known as the quasi clique merger method to cluster these web pages using a derived hierarchical tree. The experimental results show that this new similarity measurement and hierarchical clustering algorithm gives an improvement over traditional link based clustering methods.

In this extended abstract, a novel approach is proposed for text pattern recognition. Instead of the traditional models which are mainly based on the frequency of keywords for text document classification, we introduce a new graph theory model which is constructed based on both information about frequency and position of keywords. We applied this new idea to the detection of fraudulent emails written by the same person, and plagiarized publications. The results on these case studies show that this new method performs much better than traditional methods.

A graph G is called CIS if each maximal clique intersects each maximal stable set in G and is called almost CIS if it has a unique disjoint pair $(C,S)$ consisting of a maximal clique C and a maximal stable set S. While it is still unknown if there exists a good structural characterization of all CIS graphs, in this note we prove the following Andrade–Boros–Gurvich conjecture: A graph is almost CIS if and only if it is a split graph with a unique split partition.

The following open problem was proposed by Archdeacon: Characterize all graphical sequences $\pi$ such that some realization of $\pi$ admits a nowhere-zero 3-flow. The purpose of this paper is to resolve this problem and present a complete characterization: A graphical sequence $\pi = (d_1,d_2,\dots,d_n)$ with minimum degree at least two has a realization that admits a nowhere-zero 3-flow if and only if $\pi \neq (3^4,2)$, $(k,3^k)$, $(k^2,3^{k-1})$, where k is an odd integer.

Clustering method is one of the most important tools in statistics. In a graph theory model, clustering is the process of finding all dense subgraphs. A mathematically well-defined measure for graph density is introduced in this article as follows. Let G = ( V , E ) be a graph (or multi-graph) and H be a subgraph of G . The dynamic density of H is the greatest integer k such that min ∀ P {| E ( H / P )|/| V ( H / P )| − 1} > k where the minimum is taken over all possible partitions P of the vertex set of H , and H / P is the graph obtained from H by contracting each part of P into a single vertex. A subgraph H of G is a level- k community if H is a maximal subgraph of G with dynamic density at least k . An algorithm is designed in this paper to detect all level- h communities of an input multi-graph G . The worst-case complexity of this algorithm is upper bounded by O (| V ( G )| 2 h 2 ). This new method is one of few available clustering methods that are mathematically well-defined, supported by rigorous mathematical proof and able to achieve the optimization goal with polynomial complexity. As a byproduct, this algorithm also can be applied for finding edge-disjoint spanning trees of a multi-graph. The worst-case complexity is lower than all known algorithms for multi-graphs.

We prove that every Cayley graph on a finite solvable group admits a nowhere-zero 4-flow. In particular, every cubic Cayley graph on a solvable group is 3-edge-colorable.

Let $G = ( V,E )$ be a simple graph such that the number of odd vertices of G is $| V_0 |$ and the minimum odd degree is $\delta _0 $. This paper proves that the number of edges in a smallest parity subgraph of G is at most $| V | - {\text{Min}} \{ \delta _{0} , | V | - | V_0 | /2 \}$. Consequently, some results about the shortest cycle cover problem due to Itai and Rodeh, Fan, Zhang, Raspaud, Zhao are generalized. If G is a 2-edge-connected simple graph such that either G admits a nowhere-zero 4-flow or G contains no subdivision of the Petersen graph, then the total length of a shortest cycle cover of G is at most $| E | + | V | - {\text{Min}} \{ \delta _{0} , | V | - | V_0 |/2 \}$.

An independent set $J_c $ of a graph G is called critical if \[ | J_c | - | N ( J_c ) | = \max \{ | J | - | N ( J ) |:J\,\text{is an independent set of }G \}, \] and a vertex subset $U_c $ is called critical if \[ | U_c | - | N ( U_c ) | = \max \{ | U | - | N ( U ) |:U\,\text{is a vertex subset of }G \} . \] In this paper, it will be shown that finding a critical independent set and a critical vertex subset of a graph are solvable in polynomial time.