1,244 results on '"signed graph"'
Search Results
2. On 1-2-3 Conjecture-like problems in 2-edge-coloured graphs
- Author
-
Bensmail, Julien, Hocquard, Hervé, Marcille, Clara, and Meyer, Sven
- Published
- 2025
- Full Text
- View/download PDF
3. Triangle-free signed graphs with small negative inertia index
- Author
-
Duan, Fang and Yang, Yuhong
- Published
- 2024
- Full Text
- View/download PDF
4. On Spectrum of Neighbourhood Corona Product of Signed Graphs
- Author
-
Sonar, Bishal, Guragain, Satyam, Srivastava, Ravi, Patel, Manoj Kumar, editor, Ashraf, Mohammad, editor, Mahdou, Najib, editor, and Kim, Hwankoo, editor
- Published
- 2025
- Full Text
- View/download PDF
5. Evolution of Self-confidence in Opinion Dynamics over Signed Network
- Author
-
Bhowmick, Sourav and Panja, Surajit
- Published
- 2020
- Full Text
- View/download PDF
6. Output sign-consensus of heterogenous multi-agent systems: an observer-based approach
- Author
-
Sun, Zhenyu and Zhang, Hongwei
- Published
- 2020
- Full Text
- View/download PDF
7. Distributed Finite-time Bipartite Consensus of Multi-agent Systems via Event-triggered Control
- Author
-
Xu, Peng, Wang, Xinyu, Xie, Guangming, Tao, Jin, Xu, Minyi, and Zhou, Quan
- Published
- 2020
- Full Text
- View/download PDF
8. Turán problem of signed graph for negative odd cycle.
- Author
-
Wang, Junjie, Hou, Yaoping, and Huang, Xueyi
- Abstract
We investigate natural Turán problems on signed graphs in this paper. Let C 2 k + 1 − denote the signed cycle of length 2 k + 1 with one negative edge. We determine the maximum number of edges among all unbalanced signed graphs of order n with no subgraph switching to C 2 k + 1 − , where 3 ≤ k ≤ n 10 − 1 , and characterize the extremal signed graphs. As a by-product, we also obtain the maximum spectral radius among these signed graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2025
- Full Text
- View/download PDF
9. Net Laplacian spectrum of some products built on the simple corona of a signed graph.
- Author
-
Pirzada, S., Riyaz ul Rashid, Mir, and Stanić, Zoran
- Subjects
- *
LAPLACIAN matrices , *MATRICES (Mathematics) - Abstract
For a signed graph Σ, if A(Σ) and D±(Σ) are its adjacency matrix and diagonal matrix of net degrees, then the net Laplacian matrix of Σ is N(Σ) = D±(Σ) − A(Σ). A simple corona Σ ∘ K1 is obtained by attaching a positive pendant edge at every vertex of Σ. In this paper, we define the three products of signed graphs Σ1 and Σ2 based on the simple corona Σ1 ∘ K1, and compute their net Laplacian spectrum when Σ1 is net-regular. As an application, we consider the controllability of the corresponding products. [ABSTRACT FROM AUTHOR]
- Published
- 2025
- Full Text
- View/download PDF
10. The determinant of {±1}-matrices and oriented hypergraphs.
- Author
-
Rusnak, Lucas J., Reynes, Josephine, Li, Russell, Yan, Eric, and Yu, Justin
- Subjects
- *
HADAMARD matrices , *ABSOLUTE value , *GENERALIZATION , *MATRICES (Mathematics) , *FAMILIES - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
11. Encryption and decryption of signed graph matrices through RSA algorithm.
- Author
-
Wardak, Obaidullah, Sinha, Deepa, and Sethi, Anshu
- Abstract
Information security and confidentiality are burning issues in today's digitally connected world. Encryption is considered a fast-moving trend in this reference. Although we see rigorous enhancements in the development of information security tools, storage and retrieval, enormous challenges still occur due to unsecured transmission channels, hacking tools and the ubiquity of the Internet. This paper proposes a new cryptography mechanism for secure data transmission and retrieval using a signed graph, its adjacency matrix and the RSA algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
12. Zeta functions of signed graphs.
- Author
-
Li, Deqiong, Hou, Yaoping, and Wang, Dijian
- Subjects
- *
ZETA functions , *DIRECTED graphs , *REGULAR graphs , *LOGICAL prediction - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
13. On double domination numbers of signed complete graphs.
- Author
-
Sehrawat, Deepak
- Subjects
- *
ISOMORPHISM (Mathematics) - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
14. The Network Factor of Equity Pricing: A Signed Graph Laplacian Approach.
- Author
-
Uddin, Ajim, Tao, Xinyuan, and Yu, Dantong
- Subjects
FINANCIAL crises ,TIME-based pricing ,EXPECTED returns ,MARKET design & structure (Economics) ,PRICES - Abstract
The connections among firms exhibit heterogeneity, complexity, and dynamism, posing a challenge for traditional unsigned network models. This article proposes a signed graph Laplacian approach to construct a dynamic network index (DNI), quantifying the aggregate changes in the market network over time. A larger DNI indicates more significant changes in firms' interconnectedness and in the market network structure. Firms with higher sensitivity to DNI exhibit lower expected returns. Incorporating DNI into conventional asset pricing models improves return predictability. Results are robust for multiple estimators, various factor models, and different selections of test assets. Our findings suggest that the network factor generates a significant equity risk premium. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
15. Vector valued switching in the products of signed graphs.
- Author
-
Mathew, Albin and Germina, K. A.
- Subjects
- *
GRAPH theory , *LEXICOGRAPHY , *EDGES (Geometry) , *MATHEMATICAL bounds , *MATHEMATICAL models - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
16. Vector valued switching in signed graphs.
- Author
-
K., Shahul Hameed, Mathew, Albin, K. A., Germina, and Zaslavsky, Thomas
- Subjects
- *
GRAPHIC methods , *VECTORS (Calculus) , *DIMENSIONS , *MATHEMATICS , *GEOMETRY - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
17. On Cayley sum signed graphs-II.
- Author
-
Sharma, Deepakshi, Somra, Sachin, and Sinha, Deepa
- Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
18. On Cayley sum signed graphs-I.
- Author
-
Somra, Sachin, Sharma, Deepakshi, and Sinha, Deepa
- Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
19. Edge coloring of small signed graphs
- Author
-
Robert Janczewski, Krzysztof Turowski, and Bartłomiej Wróblewski
- Subjects
signed graph ,edge coloring of signed graph ,Information technology ,T58.5-58.64 - Abstract
In 2020, Behr introduced the problem of edge coloring of signed graphs and proved that every signed graph (G, sigma) can be colored using Delta(G) or Delta(G) + 1 colors, where Delta(G) denotes the maximum degree of G. Three years later, Janczewski et al. introduced a notion of signed class 1, such that a graph G is of signed class 1 if and only if every signed graph (G, sigma) can be colored using Delta(G) colors. It is a well-known fact that almost all graphs are of class 1. In this paper we conjecture that the similar fact is true for signed class 1, that almost all graphs are of signed class 1. To support the hypothesis we implemented an application that colored all the signed graphs with at most 8 vertices. We describe an algorithm behind the application and discuss the results of conducted experiments.
- Published
- 2025
20. Design of Event-Triggered Secure Containment Controllers for Multi-Agent Systems over Signed Graphs
- Author
-
Zheng, Shaobo and Zhou, Lei
- Published
- 2025
- Full Text
- View/download PDF
21. Optimal Network Pairwise Comparison.
- Author
-
Jin, Jiashun, Ke, Zheng Tracy, Luo, Shengming, and Ma, Yucong
- Subjects
- *
PHASE transitions , *ASYMPTOTIC normality , *GENE regulatory networks , *HETEROGENEITY , *PROBABILITY theory - Abstract
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. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work. [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF
22. Signed graphs with exactly two distinct main eigenvalues.
- Author
-
Du, Zenan, You, Lihua, Liu, Hechao, and Yuan, Xiying
- Subjects
- *
EIGENVALUES , *GRAPH theory , *ORTHOGONAL functions , *REGULAR graphs - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
23. Circular flows in mono‐directed signed graphs.
- Author
-
Li, Jiaao, Naserasr, Reza, Wang, Zhouningxin, and Zhu, Xuding
- Subjects
- *
DIRECTED graphs , *EULERIAN graphs , *PLANAR graphs , *GRAPH coloring , *FLOWGRAPHS , *BIPARTITE graphs , *HOMOMORPHISMS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
24. نتایجی در باب گرافهای کامل علامت دار.
- Author
-
فریده حیدری
- Subjects
GRAPH connectivity ,POLYNOMIALS ,EIGENVALUES ,CACTUS ,TRIANGLES - Abstract
Introduction Let G be a simple graph, V(G) and E(G) be its vertex set and edge set, respectively. Then n = |V(G)| is called the order of G. By K
n , we denote the complete graph of order n. The disjoint union of t complete graphs K2 is denoted by tK2 . Also, K1,n denotes the star graph of order n + 1. A cactus is a connected graph in which no edge lies on more than one cycle. The cactus graph with k edges and t cycles (triangles), depicted in Fig. 1, is denoted by Gt (G0 is the star graph K1,k ). A simple graph G (underlying graph) with a sign function σ ∶ E(G) → {–,+} is called a signed graph and denoted by Γ = (G, σ). If all edges of Γ are positive (resp. negative), then Γ is denoted by (G,+) (resp. (G,–)). By Γ[X],we denote the subgraph induced by X, where X is a subset of V(Γ). Let (Kn , H– ) be a signed complete graph whose negative edges induce a subgraph H. If H is a disjoint union of two graphs H1 and H2 , then (Kn , H– ) is denoted by (Kn , H1 – U H2 – ). The characteristic polynomial of a matrix A is denoted by φ(A). We denote the adjacency matrix of a signed graph Γ by A(Γ). The characteristic polynomial of A(Γ) is called the characteristic polynomial of Γ and is denoted by φ(Γ, λ). Also, the eigenvalues of A(Γ) are called the eigenvalues of Γ. The largest eigenvalue of Γ is called the index and denoted by λ1 (Γ). There are many papers on the characteristic polynomials and eigenvalues of signed graphs, for instance [3, 13, 14, 15]. In [2], the characteristic polynomial of (Kn , G0 – ) was computed. In [12], the authors determined the characteristic polynomial of (Kn , G1 – ). In this paper, we study the characteristic polynomial of the signed complete graph (Kn , H– U tK2 – ), where H is an arbitrary subgraph of Kn . As a corollary, we find the characteristic polynomial of Γ = (Kn , Gt – ) for every t ≥ 0, and provide a sharp bound for the index of Γ. Characteristic polynomial The matrix Js is all-one matrix of order s, and js = (1, …,1)T ∈ ℝs . Theorem 1. Let Γ = (Kn , H– U tK2 – ) be a signed complete graph, where t ≥ 1 and H is a subgraph of Kn . Then φ(Γ, λ) = (λ – 1)t (λ + 3)t–1 φ ([2t – 3 j , σ) be a signed graph and ⊓= {Xn–2t T 2tj n–2t A(K ) ]). Definition 3 [12]. Let Γ = (Kn–2t , H– n , σ) be a signed graph and ⊓= {X1 , …, Xp , Xp+1 , …, Xp+q } be a partition of V(Γ) such that all edges between Xi and Xj have the same sign, for each i,j. Also, Γ[Xi ] = (Kni ,+) for i = 1, …, p, and Γ[Xi ] = (Kni ,–) for i = p +1, …, p + q, where |Xi | = ni for i = 1, …, p +q. Obviously, ⊓ is an equitable partition of V(Γ). The partition ⊓ is called a special partition of V(Γ). Theorem 4. Let Γ = (Kn , H– U tK2 – ) be a signed complete graph, where t ≥ 1 and H is a subgraph of Kn. Let ⊓= {X1 , …, Xp , Xp+1 , …, Xp+q } be a special partition of V(Kn–2t , H– ), m1 = ∑i=1 p ni and m2 = ∑i=p+1 p+q ni . If B is the quotient matrix of A(Γ) related to {V(tK2 )} U ⊓, then φ(Γ, λ) = (λ + 1)m (λ – 1)1 –pt+m (λ + 3)2 –qt–1 φ(B). Corollary 5. Let Γ = (Kn , H– ) be a signed complete graph, where H is a subgraph of Kn. Let ⊓= {X1 , …, Xp , Xp+1 , …, Xp+q } be a special partition of V(Kn , H– ), m1 = ∑p i=1 ni and m2 = ∑p+q i=p+1 ni . If B is the quotient matrix of A(Γ) related to ⊓, then φ(Γ, λ) = (λ + 1)m (λ – 1)1 –pm φ(B). Theorem 6. Let Γ = (K2 –qn , Gt – ) be a signed complete graph, where Gt is the cactus graph with k edges and t ≥ 1 cycles, depicted in Fig. 1. If u = |V(Kn )\V(Gt )| ≥ 1, then φ(Γ, λ) = (λ + 1)n–2t–3 (λ – 1)t (λ + 3)t–1 (λ4 + (6 – n)λ³ + (12 + 4t – 5n)λ² + (10 + 8t –7n + 4ku –4tu)λ + 3+ 4t –3n + 12ku – 28tu). Remark 9. By [1, Theorem 2] and [2, Lemma 3], Theorem 6 holds for u = 0 and t = 0. A Sharp Bound for the Index In this section, by using the Interlacing Theorem, we find a sharp lower bound for the index of Γ = (Kn , Gt – ) . Theorem 11. Let Γ = (Kn , Gt – ) be a signed complete graph, where Gt is the cactus graph with k edges and t cycles, depicted in Fig. 1. Then n – 5+ √(n + 1)² – 16t/2 ≤ λ1 (Γ). Moreover, if n = 4t and k = 3t, then λ1 (Γ) = n –3 and the equality holds. Conclusion In this paper, we investigated the characteristic polynomial of the signed complete graph (Kn , H– U tK2 – ), where H is an arbitrary subgraph of Kn is the cactus graph depicted in Fig. 1. In [12], the authors conjectured that among all signed complete graphs of order n > 5 whose negative edges induce a cactus graph with k edges and t cycles, the signed graph Γ = (Kn , Gt – ) is computed and a sharp bound for the index of Γ is provided, where Gt is the cactus graph depicted in Fig. 1. In [12], the authors conjectured that among all signed complete graphs of order n > 5 whose negative edges induce a cactus graph with k edges and t cycles, the signed graph Γ = (Kn , Gt – ) has the maximum index. The findings related to Γ provide a foundation for examining the proposed conjecture. [ABSTRACT FROM AUTHOR]- Published
- 2024
25. Spectral Turán problem for [formula omitted]-free signed graphs.
- Author
-
Wang, Yongang
- Subjects
- *
EIGENVALUES - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
26. Integer flows on triangularly connected signed graphs.
- Author
-
Li, Liangchen, Li, Chong, Luo, Rong, and Zhang, Cun‐Quan
- Abstract
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≤i
i+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] - Published
- 2024
- Full Text
- View/download PDF
27. SPECTRAL ANALYSIS OF ARITHMETIC FUNCTION SIGNED GRAPHS.
- Author
-
ALFRAN, HOWIDA ADEL, RAJENDRA, R., REDDY, P. SIVA KOTA, KEMPARAJU, R., and ALTOUM, SAMI H.
- Subjects
ARITHMETIC functions ,GRAPH theory ,GRAPHIC methods ,EIGENVALUES ,CHARTS, diagrams, etc. - Abstract
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]
- Published
- 2024
28. Finite/Fixed-Time Controls for Neural Networks with Distributed Delays in the Signed Graph
- Author
-
Yang, Huabo, Sun, Wen, Chinese Institute of Command and Control, Angrisani, Leopoldo, Series Editor, Arteaga, Marco, Series Editor, Chakraborty, Samarjit, Series Editor, Chen, Shanben, Series Editor, Chen, Tan Kay, Series Editor, Dillmann, Rüdiger, Series Editor, Duan, Haibin, Series Editor, Ferrari, Gianluigi, Series Editor, Ferre, Manuel, Series Editor, Jabbari, Faryar, Series Editor, Jia, Limin, Series Editor, Kacprzyk, Janusz, Series Editor, Khamis, Alaa, Series Editor, Kroeger, Torsten, Series Editor, Li, Yong, Series Editor, Liang, Qilian, Series Editor, Martín, Ferran, Series Editor, Ming, Tan Cher, Series Editor, Minker, Wolfgang, Series Editor, Misra, Pradeep, Series Editor, Mukhopadhyay, Subhas, Series Editor, Ning, Cun-Zheng, Series Editor, Nishida, Toyoaki, Series Editor, Oneto, Luca, Series Editor, Panigrahi, Bijaya Ketan, Series Editor, Pascucci, Federica, Series Editor, Qin, Yong, Series Editor, Seng, Gan Woon, Series Editor, Speidel, Joachim, Series Editor, Veiga, Germano, Series Editor, Wu, Haitao, Series Editor, Zamboni, Walter, Series Editor, and Tan, Kay Chen, Series Editor
- Published
- 2024
- Full Text
- View/download PDF
29. Offensive Alliances in Signed Graphs
- Author
-
Feng, Zhidan, Fernau, Henning, Mann, Kevin, Qi, Xingqin, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Chen, Xujin, editor, and Li, Bo, editor
- Published
- 2024
- Full Text
- View/download PDF
30. On Heuristic Algorithm with Greedy Strategy for the Correlation Clustering Problem Solution
- Author
-
Soldatenko, Aleksandr, Semenova, Daria, Ibragimova, Ellada, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Vishnevskiy, Vladimir M., editor, Samouylov, Konstantin E., editor, and Kozyrev, Dmitry V., editor
- Published
- 2024
- Full Text
- View/download PDF
31. Balanced Hop-Constrained Path Enumeration in Signed Directed Graphs
- Author
-
Tang, Zhiyang, Wang, Jinghao, Wu, Yanping, Wang, Xiaoyang, Qin, Lu, Zhang, Ying, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Bao, Zhifeng, editor, Borovica-Gajic, Renata, editor, Qiu, Ruihong, editor, Choudhury, Farhana, editor, and Yang, Zhengyi, editor
- Published
- 2024
- Full Text
- View/download PDF
32. Computing the determinant of a signed graph
- Author
-
Alshamary Bader and Stanić Zoran
- Subjects
signed graph ,characteristic polynomial ,eigenvalues ,determinant ,bicyclic graph ,chain graph ,05c50 ,05c22 ,Mathematics ,QA1-939 - Abstract
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.
- Published
- 2024
- Full Text
- View/download PDF
33. Signed Zero-Divisor Graphs Over Commutative Rings
- Author
-
Lu, Lu, Feng, Lihua, and Liu, Weijun
- Published
- 2024
- Full Text
- View/download PDF
34. Matrix tree theorem for the net Laplacian matrix of a signed graph.
- Author
-
Mallik, Sudipta
- Subjects
- *
LAPLACIAN matrices , *SPANNING trees , *MATRICES (Mathematics) , *TREES - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
35. Correlation Clustering Problem Under Mediation.
- Author
-
Ales, Zacharie, Engelbeen, Céline, and Figueiredo, Rosa
- Subjects
- *
DATA libraries , *POLARIZATION (Social sciences) , *RANDOM graphs , *TREE size , *SOCIAL networks , *INTEGER programming - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
36. On the packing number of antibalanced signed simple planar graphs of negative girth at least 5.
- Author
-
Naserasr, Reza and Yu, Weiqiang
- Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
37. On derived t-path, t=2,3 signed graph and t-distance signed graph
- Author
-
Sinha, Deepa and Somra, Sachin
- Published
- 2025
- Full Text
- View/download PDF
38. Additively graceful signed graphs
- Author
-
Jessica Pereira, Tarkeshwar Singh, and S. Arumugam
- Subjects
Signed graph ,graceful graph ,additively graceful graph ,05C 22 ,05C 78 ,Mathematics ,QA1-939 - Abstract
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.
- Published
- 2023
- Full Text
- View/download PDF
39. Signed Ramsey Numbers.
- Author
-
Mutar, Mohammed A., Sivaraman, Vaidy, and Slilaty, Daniel
- Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
40. Signed distance Laplacian matrices for signed graphs.
- Author
-
Roy, Roshni T., Germina, K. A., Hameed K, Shahul, and Zaslavsky, Thomas
- Subjects
- *
WEIGHTED graphs , *LAPLACIAN matrices , *MATRICES (Mathematics) - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
41. Spectral Analysis of Splitting Signed Graph.
- Author
-
Kumar, Sandeep and Sinha, Deepa
- Subjects
- *
LAPLACIAN matrices , *EIGENVECTORS , *EIGENVALUES , *ALGORITHMS - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
42. WSGMB: weight signed graph neural network for microbial biomarker identification.
- Author
-
Pan, Shuheng, Jiang, Xinyi, and Zhang, Kai
- Subjects
- *
CONVOLUTIONAL neural networks , *CROHN'S disease , *BIOMARKERS , *IDENTIFICATION , *GRAPH algorithms , *WEIGHTED graphs , *GUT microbiome - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
43. Estimating distance between an eigenvalue of a signed graph and the spectrum of an induced subgraph.
- Author
-
Stanić, Zoran
- Subjects
- *
EIGENVALUES , *EIGENVECTORS , *REGULAR graphs - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
44. Representations of signed graphs.
- Author
-
Chen, Yu Qing, Evans, Anthony B., Liu, Xiaoyu, Slilaty, Daniel C., and Zhou, Xiangqian
- Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
45. An Alternative Technique to Find the Spectrum and Laplacian Spectrum of a Cartesian Product of Signed Graphs
- Author
-
Kaur, Bableen, Kumar, Sandeep, and Sinha, Deepa
- Published
- 2024
- Full Text
- View/download PDF
46. Net Laplacian eigenvalues of certain corona-like products of signed graphs
- Author
-
Shamsher, Tahir, Pirzada, S., and Stanić, Zoran
- Published
- 2024
- Full Text
- View/download PDF
47. On colorings and orientations of signed graphs
- Author
-
Daniel Slilaty
- Subjects
signed graph ,signed-graph coloring ,orientation ,bidirection ,Mathematics ,QA1-939 - Published
- 2023
- Full Text
- View/download PDF
48. On -gain graphs with few positive eigenvalues.
- Author
-
He, Xiaocong, Feng, Lihua, and Lu, Lu
- Subjects
- *
EIGENVALUES , *REGULAR graphs - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
49. Relations between the skew spectrum of an oriented graph and the spectrum of an associated signed graph.
- Author
-
Stanić, Zoran
- Subjects
- *
DIRECTED graphs , *BIPARTITE graphs - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
50. Separating signatures in signed planar graphs.
- Author
-
Naserasr, Reza and Yu, Weiqiang
- Subjects
- *
PLANAR graphs , *GRAPH theory - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.