Search

Let Γ = (G , σ) be a signed graph with underlying graph G and sign function σ : E (G) → { + , − }. The number of negative eigenvalues (including multiplicities) of Γ , denoted by n (Γ) , is called the negative inertia index of Γ. In this paper, we characterize the signed graphs Γ with n (Γ) = 1 , and the triangle-free signed graphs Γ with n (Γ) = 2 , respectively. [ABSTRACT FROM AUTHOR]

We introduce the zeta function of a signed graph and give a determinant expression for it in terms of the signed oriented line graph, and moreover, we obtain some properties of the zeta function of a signed graph. As applications we affirm the conjecture proposed by Sato [Weighted zeta functions of graph coverings, Electronic J. Combin. 13 (2006), #91] and give a method to construct a family of cospectral signed digraphs. Additionally, we show that two connected regular signed graphs have the same zeta function if and only if they are cospectral. [ABSTRACT FROM AUTHOR]

Let Σ = (G,σ) be a signed graph with a vertex set V (G). A set D ⊆ V (G) is said to be a double dominating set of Σ if it satisfies the following conditions: (i) |N[v] ∩ D|≥ 2 for each v ∈ V (G), and (ii) Σ[D,Dc] is balanced, where N[v] denotes the closed neighborhood of v and Σ[D,Dc] denotes the subgraph induced by the edges of Σ with one end vertex in D and the other end vertex in Dc. The minimum size among all the double dominating sets of Σ is the double domination number γ×2(Σ) of Σ. In this study, we investigated this parameter for signed complete graphs. We prove that, for n ≥ 5, if (Kn,σ) is a signed complete graph, then 2 ≤ γ×2(Kn,σ) ≤ n − 1 and these bounds are sharp. Moreover, for all signed complete graphs over Kn we determined their possible double domination numbers. Finally, we compute the double domination numbers of all signed complete graphs of orders up to six. [ABSTRACT FROM AUTHOR]

A signed graph is a graph whose edges are labeled either as positive or negative. The concepts of vector valued switching and balancing dimension of signed graphs were introduced by S. Hameed et al. In this paper, we deal with the balancing dimension of various products of signed graphs, namely the Cartesian product, the lexicographic product, the tensor product, and the strong product. [ABSTRACT FROM AUTHOR]

A signed graph is a graph with edges marked positive and negative; it is unbalanced if some cycle has negative sign product. We introduce the concept of vector valued switching function in signed graphs, which extends the concept of switching to higher dimensions. Using this concept, we define balancing dimension and strong balancing dimension for a signed graph, which can be used for a new classification of degree of imbalance of unbalanced signed graphs. We provide bounds for the balancing and strong balancing dimensions, and calculate these dimensions for some classes of signed graphs. [ABSTRACT FROM AUTHOR]

The Cayley sum graph is a graph whose vertex comprises elements of an abelian group G and edges are the sum of these vertices belonging to a subset of G, namely, S. We introduce Cayley sum signed graph by giving the sign to these edges. An edge receives a positive sign if any of the incident vertices belong to S; otherwise, it receives a negative sign. We discuss the balance, clusterability and some properties of derived Cayley sum signed graph. [ABSTRACT FROM AUTHOR]

The Cayley sum graph is a graph whose vertex comprises elements of an abelian group G, and edges are the sum of these vertices belonging to a subset of G, namely, S. We introduce the Cayley sum signed graph by giving the sign to these edges. An edge receives a positive sign if any of the incident vertices belong to S. Otherwise, it receives a negative sign. We discuss the properties of the Cayley sum signed graph. [ABSTRACT FROM AUTHOR]

The determinants of { ± 1 } -matrices are calculated via the oriented hypergraphic Laplacian and summing over incidence generalizations of vertex cycle-covers. These cycle-covers are signed and partitioned into families based on their hyperedge containment. Every non-edge-monic family is shown to contribute a net value of 0 to the Laplacian, while each edge-monic family is shown to sum to the absolute value of the determinant of the original incidence matrix. Simple symmetries are identified as well as their relationship to Hadamard's maximum determinant problem. Finally, the entries of the incidence matrix are reclaimed using only the signs of an adjacency-minimal set of cycle-covers from an edge-monic family. [ABSTRACT FROM AUTHOR]

AbstractWe are interested in the problem of two-sample network hypothesis testing: given two networks with the same set of nodes, we wish to test whether the underlying Bernoulli probability matrices of the two networks are the same or not. We propose Interlacing Balance Measure (IBM) as a new two-sample testing approach. We consider the Degree-Corrected Mixed-Membership (DCMM) model for undirected networks, where we allow severe degree heterogeneity, mixed-memberships, flexible sparsity levels, and weak signals. In such a broad setting, how to find a test that has a tractable limiting null and optimal testing performances is a challenging problem. We show that IBM is such a test: in a broad DCMM setting with only mild regularity conditions, IBM has N(0,1) as the limiting null and achieves the optimal phase transition.While the above is for undirected networks, IBM is a unified approach and is directly implementable for directed networks. For a broad directed-DCMM (extension of DCMM for directed networks) setting, we show that IBM has N(0,1/2) as the limiting null and continues to achieve the optimal phase transition. We have also applied IBM to the Enron email network and a gene co-expression network, with interesting results. [ABSTRACT FROM AUTHOR]

An eigenvalue λ of a signed graph S of order n is a main eigenvalue if its eigenspace is not orthogonal to the all-ones vector j. Characterizing signed graphs with exactly k (1 ≤ k ≤ n) main eigenvalues is a problem in algebraic and graph theory that has been studied since 2020. Z. Stanić has noticed that a signed graph has exactly one main eigenvalue if and only if it is net-regular, and in this paper, we study signed graphs with exactly two distinct main eigenvalues by studying (0 , 1 , 2) -multi-graphs with exactly two distinct main eigenvalues. We partially characterize the case when the basic graphs of the (0 , 1 , 2) -multi-graphs are trees, and propose some problems for further research. [ABSTRACT FROM AUTHOR]

In this paper, the concept of circular r $r$‐flow in a mono‐directed signed graph (G,σ) $(G,\sigma)$ is introduced. That is a pair (D,f) $(D,f)$, where D $D$ is an orientation on G $G$ and f:E(G)→(−r,r) $f:E(G)\to (-r,r)$ satisfies that ∣f(e)∣∈[1,r−1] $| f(e)| \in [1,r-1]$ for each positive edge e $e$ and ∣f(e)∣∈[0,r2−1]∪[r2+1,r) $| f(e)| \in [0,\frac{r}{2}-1]\cup [\frac{r}{2}+1,r)$ for each negative edge e $e$, and the total in‐flow equals the total out‐flow at each vertex. This is the dual notion of circular colorings of signed graphs and is distinct from the concept of circular flows in bi‐directed graphs associated with signed graphs studied in the literature. We first explore the connection between circular 2kk−1 $\frac{2k}{k-1}$‐flows and modulo k $k$‐orientations in signed graphs. Then we focus on the upper bounds for the circular flow indices of signed graphs in terms of the edge‐connectivity, where the circular flow index of a signed graph is the minimum value r $r$ such that it admits a circular r $r$‐flow. We prove that every 3‐edge‐connected signed graph admits a circular 6‐flow and every 4‐edge‐connected signed graph admits a circular 4‐flow. More generally, for k≥2 $k\ge 2$, we show that every (3k−1) $(3k-1)$‐edge‐connected signed graph admits a circular 2kk−1 $\frac{2k}{k-1}$‐flow, every 3k $3k$‐edge‐connected signed graph has a circular r $r$‐flow with r<2kk−1 $r\lt \frac{2k}{k-1}$, and every (3k+1) $(3k+1)$‐edge‐connected signed graph admits a circular 4k+22k−1 $\frac{4k+2}{2k-1}$‐flow. Moreover, the (6k−2) $(6k-2)$‐edge‐connectivity condition is shown to be sufficient for a signed Eulerian graph to admit a circular 4k2k−1 $\frac{4k}{2k-1}$‐flow, and applying this result to planar graphs, we conclude that every signed bipartite planar graph of negative girth at least 6k−2 $6k-2$ admits a homomorphism to the negative even cycles C−2k ${C}_{-2k}$. [ABSTRACT FROM AUTHOR]

The classical spectral Turán problem is to determine the maximum spectral radius of an F -free graph of order n. Let K k − be the set of all unbalanced K k. Wang, Hou and Li [25] and Chen and Yuan [10] studied the existence of unbalanced K 3 and K 4 , respectively. In this paper, we focus on the spectral Turán problem of K k − -free signed graph for k ≥ 5. By using a different method, we give an answer for k = 5 and completely characterize the corresponding extremal signed graph. [ABSTRACT FROM AUTHOR]

A triangle‐path in a graph G $G$ is a sequence of distinct triangles T1,T2,...,Tm ${T}_{1},{T}_{2},\ldots ,{T}_{m}$ in G $G$ such that for any i,j $i,j$ with 1≤ii+1 $j\gt i+1$. A connected graph G $G$ is triangularly connected if for any two nonparallel edges e $e$ and e′ $e^{\prime} $ there is a triangle‐path T1T2⋯Tm ${T}_{1}{T}_{2}\cdots {T}_{m}$ such that e∈E(T1) $e\in E({T}_{1})$ and e′∈E(Tm) $e^{\prime} \in E({T}_{m})$. For ordinary graphs, Fan et al. characterize all triangularly connected graphs that admit nowhere‐zero 3‐flows or 4‐flows. Corollaries of this result include the integer flow of some families of ordinary graphs, such as locally connected graphs due to Lai and some types of products of graphs due to Imrich et al. In this paper, Fan's result for triangularly connected graphs is further extended to signed graphs. We proved that a flow‐admissible triangularly connected signed graph admits a nowhere‐zero 4‐flow if and only if it is not the wheel W5 ${W}_{5}$ associated with a specific signature. Moreover, this result is sharp since there are infinitely many unbalanced triangularly connected signed graphs admitting a nowhere‐zero 4‐flow but no 3‐flow. [ABSTRACT FROM AUTHOR]

In this paper, we discuss spectrum and energy of Arithmetic function signed graphs with respect to an arithmetical function and present some results. [ABSTRACT FROM AUTHOR]

A signed graph is a simple graph in which every edge has a positive or negative sign. In this article, we employ several algebraic techniques to compute the determinant of a signed graph in terms of the spectrum of a vertex-deleted subgraph. Particular cases, including vertex-deleted subgraphs without repeated eigenvalues or singular vertex-deleted subgraphs are considered. As applications, an algorithm for the determinant of a signed graph with pendant edges is established, the determinant of a bicyclic graph and the determinant of a chain graph are computed. In the end, the uniqueness of the polynomial reconstruction for chain graphs is proved.

For a simple signed graph G with the adjacency matrix A and net degree matrix $ D^{\pm } $ D ± , the net Laplacian matrix is $ L^{\pm }=D^{\pm }-A $ L ± = D ± − A. We introduce a new oriented incidence matrix $ N^{\pm } $ N ± which can keep track of the sign as well as the orientation of each edge of G. Also $ L^{\pm }=N^{\pm }(N^{\pm })^T $ L ± = N ± (N ± ) T . Using this decomposition, we find the number of both positive and negative spanning trees of G in terms of the principal minors of $ L^{\pm } $ L ± generalizing the Matrix Tree Theorem for an unsigned graph. We present similar results for the signless net Laplacian matrix $ Q^{\pm }=D^{\pm }+A $ Q ± = D ± + A along with a combinatorial formula for its determinant. [ABSTRACT FROM AUTHOR]

In the context of community detection, correlation clustering (CC) provides a measure of balance for social networks as well as a tool to explore their structures. However, CC does not encompass features such as the mediation between the clusters, which could be all the more relevant with the recent rise of ideological polarization. In this work, we study correlation clustering under mediation (CCM), a new variant of CC in which a set of mediators is determined. This new signed graph clustering problem is proved to be NP-hard and formulated as an integer programming formulation. An extensive investigation of the mediation set structure leads to the development of two efficient exact enumeration algorithms for CCM. The first one exhaustively enumerates the maximal sets of mediators in order to provide several relevant solutions. The second algorithm implements a pruning mechanism, which drastically reduces the size of the exploration tree in order to return a single optimal solution. Computational experiments are presented on two sets of instances: signed networks representing voting activity in the European Parliament and random signed graphs. History: Accepted by Van Hentenryck, Area Editor for Pascal. Funding: This work was supported by Fondation Mathématique Jacques Hadamard [Grant P-2019-0031]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0129) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0129). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

The packing number of a signed graph (G , σ) , denoted ρ (G , σ) , is the maximum number l of signatures σ 1 , σ 2 , … , σ l such that each σ i is switching equivalent to σ and the sets of negative edges E σ i - of (G , σ i) are pairwise disjoint. A signed graph packs if its packing number is equal to its negative girth. A reformulation of some well-known conjecture in extension of the 4-color theorem is that every antibalanced signed planar graph and every signed bipartite planar graph packs. On this class of signed planar graph the case when negative girth is 3 is equivalent to the 4-color theorem. For negative girth 4 and 5, based on the dual language of packing T-joins, a proof is claimed by B. Guenin in 2002, but never published. Based on this unpublished work, and using the language of packing T-joins, proofs for girth 6, 7, and 8 are published. We have recently provided a direct proof for girth 4 and in this work extend the technique to prove the case of girth 5. [ABSTRACT FROM AUTHOR]

Let r(s, t) be the classical 2-color Ramsey number; that is, the smallest integer n such that any edge 2-colored K n contains either a monochromatic K s of color 1 or K t of color 2. Define the signed Ramsey number r ± (s , t) to be the smallest integer n for which any signing of K n has a subgraph which switches to - K s or + K t . We prove the following results. r ± (s , t) = r ± (t , s) r ± (s , t) ≥ s - 1 2 (t - 1) r ± (s , t) ≤ r (s - 1 , t - 1) + 1 r ± (3 , t) = t r ± (4 , 4) = 7 r ± (4 , 5) = 8 r ± (4 , 6) = 10 3 t 2 ≤ r ± (4 , t + 1) ≤ 3 t - 1 [ABSTRACT FROM AUTHOR]

The stability of the gut microenvironment is inextricably linked to human health, with the onset of many diseases accompanied by dysbiosis of the gut microbiota. It has been reported that there are differences in the microbial community composition between patients and healthy individuals, and many microbes are considered potential biomarkers. Accurately identifying these biomarkers can lead to more precise and reliable clinical decision-making. To improve the accuracy of microbial biomarker identification, this study introduces WSGMB, a computational framework that uses the relative abundance of microbial taxa and health status as inputs. This method has two main contributions: (1) viewing the microbial co-occurrence network as a weighted signed graph and applying graph convolutional neural network techniques for graph classification; (2) designing a new architecture to compute the role transitions of each microbial taxon between health and disease networks, thereby identifying disease-related microbial biomarkers. The weighted signed graph neural network enhances the quality of graph embeddings; quantifying the importance of microbes in different co-occurrence networks better identifies those microbes critical to health. Microbes are ranked according to their importance change scores, and when this score exceeds a set threshold, the microbe is considered a biomarker. This framework's identification performance is validated by comparing the biomarkers identified by WSGMB with actual microbial biomarkers associated with specific diseases from public literature databases. The study tests the proposed computational framework using actual microbial community data from colorectal cancer and Crohn's disease samples. It compares it with the most advanced microbial biomarker identification methods. The results show that the WSGMB method outperforms similar approaches in the accuracy of microbial biomarker identification. [ABSTRACT FROM AUTHOR]

An ordered pair Σ = (Σu, σ) is called the signed graph, where Σu = (V,E) is a underlying graph and σ is a signed mapping, called signature, from E to the sign set {+, -}. The splitting signed graph Γ(Σ) of a signed graph Σ is defined as, for every vertex u ∈ V (Σ), take a new vertex u′. Join u′ to all the vertices of Σ adjacent to u such that σΓ(u′v) = σ(u′v), u ∈ N(v). The objective of this paper is to propose an algorithm for the generation of a splitting signed graph, a splitting root signed graph from a given signed graph using Matlab. Additionally, we conduct a spectral analysis of the resulting graph. Spectral analysis is performed on the adjacency and laplacian matrices of the splitting signed graph to study its eigenvalues and eigenvectors. A relationship between the energy of the original signed graph Σ and the energy of the splitting signed graph Γ(Σ) is established. [ABSTRACT FROM AUTHOR]

A signed graph is a graph whose edges are labelled either positive or negative. Corresponding to the two signed distance matrices defined for signed graphs, we define two signed distance Laplacian matrices. We characterize singularity and calculate the rank of these matrices and find signed distance Laplacian spectra of some classes of unbalanced signed graphs. We derive most of these results by proving them more generally for weighted signed graphs. [ABSTRACT FROM AUTHOR]

The distance between an eigenvalue λ of a signed graph G ̇ and the spectrum of a signed graph H ̇ is defined as min { | λ − μ | : μ is an eigenvalue of H ̇ }. In this paper, we investigate this distance when H ̇ is a largest induced subgraph of G ̇ that does not have λ as an eigenvalue. We estimate the distance in terms of eigenvectors and structural parameters related to vertex degrees. For example, we show that | λ | | λ − μ | ≤ δ G ̇ ∖ H ̇ max { d H ̇ (i) d G ̇ − V (H ̇) (j) : i ∈ V (G ̇) ∖ V (H ̇) , j ∈ V (H ̇) , i ∼ j } , where δ G ̇ ∖ H ̇ is the minimum vertex degree in V (G ̇) ∖ V (H ̇). If H ̇ is obtained by deleting a single vertex i , this bound reduces to | λ | | λ − μ | ≤ d (i). We also consider the case in which λ is a simple eigenvalue and H ̇ is not necessarily a vertex-deleted subgraph, and the case when λ is the largest eigenvalue of an ordinary (unsigned) graph. Our results for signed graphs apply to ordinary graphs. They can be interesting in the context of eigenvalue distribution, eigenvalue location or spectral distances of (signed) graphs. [ABSTRACT FROM AUTHOR]

We extend the concept of graph representations modulo integers introduced by Erdös and Evans to graph representations over finite rings and generalize it to representations of signed graphs. We introduce several representation numbers and product dimensions of graphs and signed graphs and compute these quantities for a few special classes of signed graphs. [ABSTRACT FROM AUTHOR]

AbstractLet [Formula: see text] be a signed graph of order p and size q. Let [Formula: see text] and [Formula: see text] Let [Formula: see text] be an injective function and let [Graphic: see text]gf(uv)={|f(u)−f(v)| if uv∈E+f(u)+f(v) if uv∈E−The function f is called an additively graceful labeling of S if [Formula: see text] and [Formula: see text] In this paper we investigate the existence of additively graceful labeling of several classes of signed graphs.

Let $ \mathbb {T}_4=\{1,-1,\mathbf {i},-\mathbf {i}\} $ T 4 = { 1 , − 1 , i , − i } be the group of fourth roots of unit. A $ \mathbb {T}_4 $ T 4 -gain graph is a graph where each orientation of an edge is given a complex unit in $ \mathbb {T}_4 $ T 4 , which is the inverse of the complex unit assigned to the opposite orientation. In this paper, we characterize the structure of the $ \mathbb {T}_4 $ T 4 -gain graphs with exactly one positive eigenvalue and determine the $ \mathbb {T}_4 $ T 4 -gain graphs with cut vertices having exactly two positive eigenvalues. Our results extend some parallel ones about mixed graphs and signed graphs. [ABSTRACT FROM AUTHOR]

We say that an oriented graph G ′ = (G , σ ′) and a signed graph G ˙ = (G , σ ˙) are mutually associated if σ ˙ (i k) σ ˙ (j k) = s i k s j k holds for every pair of edges ik and jk , where (s i j) is the skew adjacency matrix of G ′. We prove that this occurs if and only if the underlying graph G is bipartite. On the basis of this result we prove that, in the bipartite case, the skew spectrum of G ′ can be obtained from the spectrum of an associated signed graph G ˙ , and vice versa. In the non-bipartite case, we prove that the skew spectrum of G ′ can be obtained from the spectrum of a signed graph associated with the bipartite double of G ′. In this way, we show that the theory of skew spectra of oriented graphs has a strong relationship with the theory of spectra of signed graphs. In particular, we demonstrate how some problems concerning oriented graphs can be considered in the framework of signed graphs. [ABSTRACT FROM AUTHOR]

A signed graph (G , σ) is a graph together with an assignment σ of signs to the edges called signature. A switching at a vertex v is to reverse the sign of each edge incident to v. Two signatures σ 1 and σ 2 on G are equivalent if one can be obtained from the other by a sequence of switchings. The packing number of a signed graph (G , σ) , denoted ρ (G , σ) , is defined to be the maximum number of signatures σ 1 , σ 2 , ... , σ l such that each σ i is switching equivalent to σ and the sets of negative edges are pairwise disjoint. The question of determining the packing number in a class of signed graphs captures or relates to some of the most prominent studies in graph theory. For example the four-colour theorem can be restated as: For every planar simple graph G we have ρ (G , −) ≥ 3. As a generalization of the packing number, instead of considering one signature and its equivalent signatures, we consider k signatures σ 1 , σ 2 , ... , σ k (not necessarily switching equivalent) and ask whether there exist signatures σ 1 ′ , σ 2 ′ , ... , σ k ′ , where σ i ′ is a switching of σ i , such that the sets of negative edges E σ i ′ − are pairwise disjoint. It is known that there exists a signed planar simple graph whose packing number is 1. Thus for a general planar graph separating two signatures is not always possible even if σ 1 = σ 2 . In this work, we prove that given planar graph G with no 4-cycle and any two signatures σ and π on G , there are switchings σ ′ and π ′ of σ and π , respectively, such that E σ ′ − ∩ E π ′ − = ∅. And as a corollary of 3-degeneracy, we could also separate two signatures on a planar graph with no triangle, or with no 5-cycle or with no 6-cycle. Moreover, we prove that one could separate three signatures on graphs of maximum average degree less than 3, in particular on planar graphs of girth at least 6. [ABSTRACT FROM AUTHOR]

A signed graph is a pair (G , Σ) , where G = (V , E) is a graph (in which parallel edges are permitted, but loops are not) with V = { 1 , ... , n } and Σ ⊆ E. The edges in Σ are called odd and the other edges of E even. If there are parallel edges, then only two edges in each parallel class are permitted, one of which is even and one of which is odd. By S (G , Σ) we denote the set of all symmetric n × n matrices A = [ a i , j ] with a i , j < 0 if i and j are connected by an even edge, a i , j > 0 if i and j are connected by an odd edge, a i , j ∈ R if i and j are connected by both an even and an odd edge, a i , j = 0 if i ≠ j and i and j are non-adjacent, and a i , i ∈ R for all vertices i. The maximum nullity M (G , Σ) of a signed graph (G , Σ) is the maximum nullity attained by any A ∈ S (G , Σ). Arav et al. gave a combinatorial characterization of 2-connected signed graphs (G , Σ) with M (G , Σ) = 2. In this paper, we give a complete combinatorial characterization of the signed graphs (G , Σ) with M (G , Σ) = 2. [ABSTRACT FROM AUTHOR]

We define the signature packing number of a signed graph (G, σ), denoted ρ(G, σ), to be the maximum number of signatures σ 1, σ 2,..., σ l such that each σ i is switching equivalent to σ and the sets E - σi, negative edges of (G, σ i), are pairwise disjoint. In this work, first in connection to recent developments on the theory of homomorphisms of signed graphs we prove that for a signed graph (G, σ), ρ(G, σ) ≥ d + 1 if and only if (G, σ) admits a homomorphism to SPC o d, where SPC o d is obtained from SPC d by adding a positive loop to every vertex. Noting that SPC d, signed projective cube of dimension d, is the signed (Cayley) graph built on Z d 2 where each pair of binary strings at hamming distance 1 are adjacent by a positive edge and those at hamming distance d are adjacent by a negative edge. In other words, SPC d is built from the hypercube of dimension d by considering all its edges as positive edges and adding a negative edge for each pair of antipodal vertices. In special cases we have: I. A simple graph G is 4-colorable if and only if ρ(G, -) ≥ 2. II. A signed bipartite graph (G, σ) maps to SP C 3 if and only if ρ(G, σ) ≥ 3 noting that SP C 3 is the same as (K 4,4, M), that is a signed graph on K 4,4 where the set of negative edges forms a perfect matching. On restriction to planar graphs, I is then a restatement of the 4-color theorem and II is implied by an unpublished work of B. Guenin. After further development of this theory of packing in signed graphs, we give an independent proof of II which works on the larger class of K 5-minor-free graphs. More precisely we prove that: Theorem. If G is a K 5-minor-free bipartite simple graph, then for any signature σ we have ρ(G, σ) ≥ 4. The statement is shown to be strictly stronger than the four-color theorem and is proved assuming it. Furthermore, we show that I cannot be extended to the class of all signed planar simple graphs. Further development, including algorithmic implications, are considered. [ABSTRACT FROM AUTHOR]

A signed graph G ˙ = (G , σ) is a graph G = (V (G) , E (G)) with vertex set V (G) and edge set E (G) , together with a function σ : E → { + 1 , − 1 } assigning a positive or negative sign to each edge. In this paper, we present a more elementary proof for the matrix-tree theorem of signed graphs, which is based on the relations between the incidence matrices and the Laplcians of signed graphs. As an application, we also obtain the results of Monfared and Mallik about the matrix-tree theorem of graphs for signless Laplacians. [ABSTRACT FROM AUTHOR]

Let λ 1 (Σ) be the largest eigenvalue of a signed graph Σ . Wang–Yan–Qian (Linear Algebra Appl 619:137–145, 2021) and Kannan–Pragada (Linear Algebra Appl 663:62–79, 2023) extended the spectral bounds of Wilf and Nikiforov for the balanced clique number of signed graphs and derived upper bounds on λ 1 (Σ) in terms of its balanced clique number. In this paper, we characterize the extremal signed graphs attaining these upper bounds. Moreover, a relationship between λ 1 (Σ) and λ 1 (Σ - v) for some v ∈ V (Σ) is included. [ABSTRACT FROM AUTHOR]

We make advances towards a structural characterisation of the signed graphs H for which the list switch H-colouring problem List-S-Hom(H) can be solved in polynomial time. We conjecture two different characterisations, the second refining the first, in the case that the graph H can be switched to a graph in which every negative edge is also positive. Using a recent proof of the first characterisations for reflexive signed graphs, by Bok et. al., we prove the second characterisation for reflexive signed graphs. We also provide several tools for reducing the problem to the bipartite case, and prove a full complexity dichotomy for a related problem. [ABSTRACT FROM AUTHOR]

In this paper, the leader‐follower architecture is constructed by combining intermittent‐influence leaders with a signed social network. Unlike a typical network with leaders where leaders are supposed to continuously influence followers, in this article, the leaders intermittently influence followers. Furthermore, the number of influences is limited. We focus on how the intermittent‐influence leaders impact the evolution of followers' opinions. The relationship between followers' opinions and the number of leader broadcasts is analyzed in detail. Then, the number of broadcasts is regarded as the cost, and the changing trend of the revenue per broadcast is obtained. The results show that as the number of broadcasts increases, the revenue per broadcast decreases gradually. Finally, the concept of assimilation is introduced to weigh the costs and benefits, and the minimum number of broadcasts required for the leader to assimilate the followers is derived. Two examples are given to demonstrate the validity of the main conclusions. [ABSTRACT FROM AUTHOR]

AbstractSome of the most comprehensively studied degree-based topological indices are the Zagreb indices. In this article, the pair of Zagreb indices have been determined for five product graphs namely tensor product, Cartesian product, lexicographic product, strong product, symmetric difference of G1 and G2 in terms of the Zagreb indices of the signed graphs of the factor graphs G1 and G2 and their orders and sizes.

Abstract In this paper, the leader‐follower architecture is constructed by combining intermittent‐influence leaders with a signed social network. Unlike a typical network with leaders where leaders are supposed to continuously influence followers, in this article, the leaders intermittently influence followers. Furthermore, the number of influences is limited. We focus on how the intermittent‐influence leaders impact the evolution of followers' opinions. The relationship between followers' opinions and the number of leader broadcasts is analyzed in detail. Then, the number of broadcasts is regarded as the cost, and the changing trend of the revenue per broadcast is obtained. The results show that as the number of broadcasts increases, the revenue per broadcast decreases gradually. Finally, the concept of assimilation is introduced to weigh the costs and benefits, and the minimum number of broadcasts required for the leader to assimilate the followers is derived. Two examples are given to demonstrate the validity of the main conclusions.

We present the first steps towards the determination of the signed graphs for which the adjacency matrix has all but at most two eigenvalues equal to ±1. Here we deal with the disconnected, the bipartite and the complete signed graphs. In addition, we present many examples which cannot be obtained from an unsigned graph or its negative by switching. [ABSTRACT FROM AUTHOR]

A signed graph Σ = (G, σ) is a graph with a sign attached to each arc. A subset S of V (Σ) is called a dominating set of Σ if |N+ (v) ∩ S| > |N- (v) ∩ S| for all v ∈ V - S. A dominating set S ⊆ V is a connected dominating set of Σ if is connected. The minimum cardinality of a connected dominating set of Σ denoted by γsc, is called the connected domination number of Σ. In this paper, we introduce the connected domination number in a signed graph Σ and study different bounds and characterization of the connected domination number in a signed graph Σ. Furthermore, we find the best possible upper and lower bounds for γ sc (Σ) + γ sc (Σ α c) where Σ is connected. [ABSTRACT FROM AUTHOR]