Search

Bouchet's 6-flow conjecture states that every flow-admissible signed graph admits a nowhere-zero 6-flow. Seymour's 6-flow theorem states that the conjecture holds for balanced signed graphs. Rollová et al. show that every flow-admissible signed graph with frustration index two admits a nowhere-zero 7-flow, where the frustration index of a signed graph is the smallest number of edges whose deletion leaves a balanced signed graph. Wang et al. improve the result to 6-flows. In this paper, we further extend these results, and confirm Bouchet's 6-flow conjecture for signed graphs with frustration index three. There are infinitely many signed graphs with frustration index three admitting a nowhere-zero 6-flow but no 5-flow. From the point of view of flow theory, signed graphs with frustration index two are very similar to those of ordinary graphs. However, there are significant differences between ordinary graphs and signed graphs with frustration index three. [ABSTRACT FROM AUTHOR]

According to Vizing's Theorem, a major question in the area of edge coloring is to determine whether a graph is Class 1 or 2. In 1984, Mohar proved that the Cartesian product G □ H is Class 1 if G is Class 1 or both G and H have a perfect matching. Recently, Behr proved that the signed graph version of Vizing's Theorem: a signed graph (G , σ) is either Class 1 or 2. Hence, we want to generalize Mohar's results to signed graphs. In this paper, we prove that (G , σ) □ (H , π) is Class 1 if one of the factors, say (G , σ) , is Class 1 and there exists an edge coloring of (G , σ) that satisfies a certain property, which is necessary as shown by an example. Let Δ-matching be a matching which covers every vertex of maximum degree. We also show that if both of (G , σ) and (H , π) have a Δ-matching and at least one of Δ (G) , Δ (H) is even, then (G , σ) □ (H , π) is Class 1. This implies that if both of G and H have a Δ-matching, then G □ H is Class 1, thereby slightly improving upon Mohar's results. [ABSTRACT FROM AUTHOR]

A graph G is strongly even cycle decomposable if for every subdivision G ′ of G with an even number of edges, the edges of G ′ can be partitioned into cycles of even length. Máčajová and Mazák asked whether the line graph of a simple 2-connected cubic graph is strongly even cycle decomposable. A result of Seymour implies that the line graph of every 2-connected planar cubic graph is strongly even cycle decomposable. In this paper, we prove that the line graphs of simple 3-connected cubic graphs embedded in the projective plane or in the torus are strongly even cycle decomposable. [ABSTRACT FROM AUTHOR]

In this paper, we deal with extremal eigenvalues of the adjacency matrices of complete signed graphs. The complete signed graphs with maximal index (i.e. the largest eigenvalue) with n vertices and m ≤ ⌊ n 2 / 4 ⌋ negative edges have been already determined. We address the remaining case by characterizing those with m > ⌊ n 2 / 4 ⌋ negative edges. We also identify the unique signed graph with maximal index among complete signed graphs whose negative edges induce a tree of diameter at least d for any given d. This extends a recent result by Li, Lin, and Meng [Discrete Math. 346 (2023), 113250] who established the same result for d = 2. Finally, we prove that the smallest minimum eigenvalue of complete signed graphs with n vertices whose negative edges induce a tree is − n 2 − 1 − 1 + O (1 n). [ABSTRACT FROM AUTHOR]

It is known that, for any k -list assignment L of an m -edge graph G , the number of L -list colorings of G is at least the number of the proper k -colorings of G when k > (m − 1) / ln ⁡ (1 + 2). In this paper, we extend the Whitney's broken cycle theorem to L -colorings of signed graphs, by which we show that if k > ( m 3 ) + ( m 4 ) + m − 1 then, for any k -assignment L , the number of L -colorings of a signed graph Σ with m edges is at least the number of the proper k -colorings of Σ. Further, if L is 0-free (resp., 0-included) and k is even (resp., odd), then the lower bound ( m 3 ) + ( m 4 ) + m − 1 for k can be improved to (m − 1) / ln ⁡ (1 + 2). [ABSTRACT FROM AUTHOR]

A signed graph is a pair Γ = (G , σ) , where x = (V (G) , E (G)) is a graph and σ : E (G) → { + 1 , − 1 } is the sign function on the edges of G. For any α ∈ [ 0 , 1 ] we consider the matrix A α (Γ) = α D (G) + (1 − α) A (Γ) , where D (G) is the diagonal matrix of the vertex degrees of G , and A (Γ) is the adjacency matrix of Γ. Let m A α (Γ) (α) be the multiplicity of α as an A α (Γ) -eigenvalue, and let G have p (G) pendant vertices, q (G) quasi-pendant vertices, and no components isomorphic to K 2. It is proved that m A α (Γ) (α) = p (G) − q (G) whenever all internal vertices are quasi-pendant. If this is not the case, it turns out that m A α (Γ) (α) = p (G) − q (G) + m N α (Γ) (α) , where m N (Γ) (α) denotes the multiplicity of α as an eigenvalue of the matrix N α (Γ) obtained from A α (Γ) taking the entries corresponding to the internal vertices which are not quasi-pendant. Such results allow to state a formula for the multiplicity of 1 as an eigenvalue of the Laplacian matrix L (Γ) = D (G) − A (Γ). Furthermore, it is detected a class G of signed graphs whose nullity – i.e. the multiplicity of 0 as an A (Γ) -eigenvalue – does not depend on the chosen signature. The class G contains, among others, all signed trees and all signed lollipop graphs. It also turns out that for signed graphs belonging to a subclass G ′ ⊂ G the multiplicity of 1 as Laplacian eigenvalue does not depend on the chosen signatures. Such subclass contains trees and circular caterpillars. [ABSTRACT FROM AUTHOR]

The gain graphs are essential generalizations of the signed graphs. They are indeed directed graphs whose edges are labeled by the elements of a group rather than just ±1. In this paper, we prove the existence of matroids arising from these graphs. Further, we study the structure of the obtained matroids as well as their relation with the generalized Hamming weights, the regularity of the ideal of circuits, and the codes. [ABSTRACT FROM AUTHOR]

Abstract A Weyl arrangement is the hyperplane arrangement defined by a root system. Saito proved that every Weyl arrangement is free. The Weyl subarrangements of type A ℓ are represented by simple graphs. Stanley gave a characterization of freeness for this type of arrangements in terms of their graph. In addition, the Weyl subarrangements of type B ℓ can be represented by signed graphs. A characterization of freeness for them is not known. However, characterizations of freeness for a few restricted classes are known. For instance, Edelman and Reiner characterized the freeness of the arrangements between type A ℓ − 1 and type B ℓ. In this paper, we give a characterization of the freeness and supersolvability of the Weyl subarrangements of type B ℓ under certain assumption. [ABSTRACT FROM AUTHOR]

Verifying a conjecture of Brewster, Foucaud, Hell and Naserasr, we show that signed ( H , Π ) -colouring is NP-complete for any signed graph ( H , Π ) whose s-core has at least 3 edges. [ABSTRACT FROM AUTHOR]

A 2-edge-colored graph or a signed graph is a simple graph with two types of edges. A homomorphism from a 2-edge-colored graph G to a 2-edge-colored graph H is a mapping φ : V (G) → V (H) that maps every edge in G to an edge of the same type in H. Switching a vertex v of a 2-edge-colored or signed graph corresponds to changing the type of each edge incident to v. There is a homomorphism from the signed graph G to the signed graph H if after switching some subset of the vertices of G there is a 2-edge-colored homomorphism from G to H. The chromatic number of a 2-edge-colored (resp. signed) graph G is the order of a smallest 2-edge-colored (resp. signed) graph H such that there is a homomorphism from G to H. The chromatic number of a class of graphs is the maximum of the chromatic numbers of the graphs in the class. We study the chromatic numbers of 2-edge-colored and signed graphs (connected and not necessarily connected) of a given bounded maximum degree. More precisely, we provide exact bounds for graphs with a maximum degree 2. We then propose specific lower and upper bounds for graphs with a maximum degree 3, 4, and 5. We finally propose general bounds for graphs of maximum degree k , for every k. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the signed graph version of Erdös problem: Is there a constant c such that every signed planar graph without k -cycles, where 4 ≤ k ≤ c , is 3-colorable and prove that each signed planar graph without cycles of length from 4 to 8 is 3-colorable. [ABSTRACT FROM AUTHOR]

It is well known that each nonnegative integral flow on a graph can be decomposed into a sum of nonnegative graphic circuit flows, which cannot be further decomposed into nonnegative integral sub-flows. This is equivalent to saying that the indecomposable flows on graphs are those graphic circuit flows. Turning from graphs to signed graphs, the indecomposable flows are much richer than those of unsigned graphs. This paper gives a complete description of indecomposable flows on signed graphs from the viewpoint of resolution of singularities by means of double covering graph. [ABSTRACT FROM AUTHOR]

A well-known theorem due to Vizing states that every graph with maximum degree Δ is Δ- or (Δ + 1) -edge-colorable. Recently, Behr extended the concept of edge coloring in a natural way to signed graphs. He also proved that an analogue of Vizing's Theorem holds for all signed graphs. Adopting Behr's definition, Zhang et al. proved that a signed planar graph G with maximum degree Δ is Δ-edge-colorable if either Δ ≥ 10 or Δ ∈ { 8 , 9 } and G contains no adjacent triangles. They also proposed the conjecture that every signed planar graph with Δ ≥ 6 is Δ-edge-colorable, as a generalization of Vizing's Planar Graph Conjecture. In this paper, we prove that every signed planar graph with Δ ≥ 8 is Δ-edge-colorable. [ABSTRACT FROM AUTHOR]

We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph (G , σ) , equipped with lists L (v) ⊆ V (H) , v ∈ V (G) , of allowed images, to a fixed target signed graph (H , π). The complexity of the similar homomorphism problem without lists (corresponding to all lists being L (v) = V (H)) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. We illustrate this difficulty by classifying the complexity of the problem when H is a tree (with possible loops). The tools we develop will be useful for classifications of other classes of signed graphs, and in a future companion paper we will illustrate this by using them to classify the complexity for certain irreflexive signed graphs. The structure of the signed trees in the polynomial cases is interesting, suggesting that the class of general signed graphs for which the problems are polynomial may have nice structure, analogous to the so-called bi-arc graphs (which characterised the polynomial cases of list homomorphisms to unsigned graphs). [ABSTRACT FROM AUTHOR]

We study homomorphism problems of signed graphs from a computational point of view. A signed graph ( G , Σ ) is a graph G where each edge is given a sign, positive or negative; Σ ⊆ E ( G ) denotes the set of negative edges. Thus, ( G , Σ ) is a 2 -edge-coloured graph with the property that the edge-colours, { + , − } , form a group under multiplication. Central to the study of signed graphs is the operation of switching at a vertex, that results in changing the sign of each incident edge. We study two types of homomorphisms of a signed graph ( G , Σ ) to a signed graph ( H , Π ) : ec-homomorphisms and s-homomorphisms. Each is a standard graph homomorphism of G to H with some additional constraint. In the former, edge-signs are preserved. In the latter, edge-signs are preserved after the switching operation has been applied to a subset of vertices of G . We prove a dichotomy theorem for s-homomorphism problems for a large class of (fixed) target signed graphs ( H , Π ) . Specifically, as long as ( H , Π ) does not contain a negative (respectively a positive) loop, the problem is polynomial-time solvable if the core of ( H , Π ) has at most two edges, and is NP-complete otherwise. (Note that this covers all simple signed graphs.) The same dichotomy holds if ( H , Π ) has no negative digons, and we conjecture that it holds always. In our proofs, we reduce s-homomorphism problems to certain ec-homomorphism problems, for which we are able to show a dichotomy. In contrast, we prove that a dichotomy theorem for ec-homomorphism problems (even when restricted to bipartite target signed graphs) would settle the dichotomy conjecture of Feder and Vardi. [ABSTRACT FROM AUTHOR]

A signed graph Σ = (G , σ) consists of a underlying graph G = (V , E) with a signature function σ : E → { − 1 , 1 }. ρ (M) denotes the M -spectral radius of Σ, where M = M (Σ) is a real symmetric graph matrix of Σ. Obviously, ρ (M) = max { λ 1 (M) , − λ n (M) }. Let A (Σ) be the adjacency matrix of Σ and (K n , H −) be a signed complete graph whose negative edges induce a subgraph H. In this paper, we first focus on a central problem in spectral extremal graph theory: which spanning tree T makes the ρ (A (Σ)) of the unbalanced (K n , T −) as large as possible? To answer the problem, we characterize the extremal signed graph with maximum λ 1 (A (Σ)) and minimum λ n (A (Σ)) among graphs of type (K n , T −) , respectively. Another matrix associated to a signed graph is the distance matrix D (Σ) defined by Hameed, Shijin, Soorya, Germina and Zaslavsky. Note that A (Σ) = D (Σ) when Σ ∈ (K n , T −). In this paper, we give upper bounds on the least distance eigenvalue of a signed graph Σ with diameter at least 2. This result implies a result proved by Lin originally conjectured by Aouchiche and Hansen. [ABSTRACT FROM AUTHOR]

We characterise signed cubic graphs that admit a nowhere-zero 3 -flow, a nowhere-zero 4 -flow, and nowhere-zero flows with values in abelian groups of order 3 and 4 . Most of our characterisations feature the concept of an antibalanced signature, one that is switching-equivalent to the all-negative signature. In particular, we prove that a signed cubic graph has a nowhere-zero 3 -flow if and only if it has a perfect matching and is antibalanced. Our results suggest several interesting problems for further investigation. [ABSTRACT FROM AUTHOR]

For a signed graph Σ = (G , σ) , Zaslavsky defined a proper coloring on Σ and showed that the function counting the number of such colorings is a quasi-polynomial with period two, that is, a pair of polynomials, one for odd values and the other for even values. In this paper, we focus on the case of odd, written as χ (Σ , x) for short. We initially give a homomorphism expression of such colorings, by which the symmetry is considered in counting the number of homomorphisms. Besides, the explicit formulas χ (Σ , x) for some basic classes of signed graphs are presented. As a main result, we give a combinatorial interpretation of the coefficients in χ (Σ , x) and present several applications. In particular, the constant term in χ (Σ , x) gives a new criterion for balancing and a characterization for unbalanced unicyclic graph. At last, we also give a tight bound for the constant term of χ (Σ , x). [ABSTRACT FROM AUTHOR]

Assume G is a graph and S is a set of permutations of positive integers. An S -labelling of G is a pair (D , σ) , where D is an orientation of G and σ : E (D) → S is a mapping which assigns to each arc e = (u , v) of D a permutation σ e ∈ S. A proper k -colouring of (D , σ) is a mapping f : V (G) → [ k ] = { 1 , 2 ,... , k } such that σ e (f (x)) ≠ f (y) for each arc e = (x , y). We say S is non-trivial if for every positive integer i , there is a permutation π ∈ S such that π (i) = i , and S is transitive if for every pair (i , j) of positive integers, there is a permutation π ∈ S such that π (i) = j or π (j) = i. The S -chromatic number of a graph G is the minimum integer k such that any S -labelling (D , σ) of G has a proper k -colouring. This paper constructs, for any non-trivial set S of permutations of integers, for any integers k , g , a graph of girth at least g and S -chromatic number greater than k. We further prove that if S is a non-trivial set of permutations of positive integers, and 2 ≤ k ′ ≤ k and g are positive integers, then the following two statements are equivalent: (1) there exists a graph of girth at least g , of chromatic number k ′ and S -chromatic number greater than k , (2) for any k ′ -subset I of [ k ] , there exist a , b ∈ I and π ∈ S such that a ≠ b and either π (a) = b or π (b) = a. As a consequence, there is a bipartite graph of arbitrary large girth and arbitrary large S -chromatic number if and only if S is transitive. In particular, there is a bipartite graph G of arbitrary large girth and arbitrary large group chromatic number. [ABSTRACT FROM AUTHOR]

Let Φ (G , σ) and Φ c (G , σ) denote the flow number and the circular flow number of a flow-admissible signed graph (G , σ) , respectively. It is known that Φ (G) = ⌈ Φ c (G) ⌉ for every unsigned graph G. Based on this fact, in 2011 Raspaud and Zhu conjectured that Φ (G , σ) − Φ c (G , σ) < 1 holds also for every flow-admissible signed graph (G , σ). This conjecture was disproved by Schubert and Steffen using graphs with bridges and vertices of large degree. In this paper we focus on cubic graphs, since they play a crucial role in many open problems in graph theory. For cubic graphs we show that Φ (G , σ) = 3 if and only if Φ c (G , σ) = 3 and if Φ (G , σ) ∈ { 4 , 5 } , then 4 ≤ Φ c (G , σ) ≤ Φ (G , σ). We also prove that all pairs of flow number and circular flow number that fulfil these conditions can be achieved in the family of bridgeless cubic graphs and thereby disprove the conjecture of Raspaud and Zhu even for bridgeless signed cubic graphs. Finally, we prove that all currently known flow-admissible graphs without nowhere-zero 5-flow have flow number and circular flow number 6 and propose several conjectures in this area. [ABSTRACT FROM AUTHOR]

An oriented hypergraph is an oriented incidence structure that extends the concepts of signed graphs, balanced hypergraphs, and balanced matrices. We introduce hypergraphic structures and techniques that generalize the circuit classification of the signed graphic frame matroid to any oriented hypergraphic incidence matrix via its locally-signed-graphic substructure. To achieve this, Camion's algorithm is applied to oriented hypergraphs to provide a generalization of reorientation sets and frustration that is only well-defined on balanceable oriented hypergraphs. A simple partial characterization of unbalanceable circuits extends the applications to representable matroids demonstrating that the difference between the Fano and non-Fano matroids is one of balance. [ABSTRACT FROM AUTHOR]

Abstract: We define four minor-closed classes of signed graphs in terms of embeddability in the annulus, projective plane, torus, and Klein bottle. We give the full list of 20 excluded minors for the smallest class and make a conjecture about the largest class. [Copyright &y& Elsevier]

Abstract: We define a signed embedding of a signed graph into real projective space to be an embedding such that an embedded cycle is 0-homologous if and only if it is balanced. We characterize signed graphs that have a linkless signed embedding. In particular, we exhibit 46 graphs that form the complete minor-minimal set of signed graphs that contain a non-split link for every signed embedding. With one trivial exception, these graphs are derived from different signings of the seven Petersen family graphs. [Copyright &y& Elsevier]

Abstract: Up to switching isomorphism, there are six ways to put signs on the edges of the Petersen graph. We prove this by computing switching invariants, especially frustration indices and frustration numbers, switching automorphism groups, chromatic numbers, and numbers of proper 1-colorations, thereby illustrating some of the ideas and methods of signed graph theory. We also calculate automorphism groups and clusterability indices, which are not invariant under switching. In the process, we develop new properties of signed graphs, especially of their switching automorphism groups. [Copyright &y& Elsevier]

Abstract: An important property of chordal graphs is that these graphs are characterized by the existence of perfect elimination orderings on their vertex sets. In this paper, we generalize the notion of perfect elimination orderings to signed graphs, and give a characterization for graphs admitting such orderings, together with characterizations restricted to some subclasses and further properties of those graphs. The definition of our generalized perfect elimination orderings is motivated by a generalization of the classical result that a so-called graphic hyperplane arrangement is free if and only if the corresponding graph is chordal. [Copyright &y& Elsevier]

Abstract: We generalise the signed Bollobás–Riordan polynomial of S. Chmutov and I. Pak [S. Chmutov, I. Pak, The Kauffman bracket of virtual links and the Bollobás–Riordan polynomial, Mos. Math. J. 7(3) (2007), 409–418] to a multivariate signed polynomial and study its properties. We prove the invariance of under the recently defined partial duality of S. Chmutov [S. Chmutov, Generalized duality for graphs on surfaces and the signed Bollobás–Riordan polynomial, J. Combin. Theory, Ser. B 99(3) (2009), 617–638. arXiv:0711.3490, doi:10.1016/j.jctb.2008.09.007] and show that the duality transformation of the multivariate Tutte polynomial is a direct consequence of it. [Copyright &y& Elsevier]

It is known that any signed series-parallel graph (G , σ) has circular chromatic number at most 10/3. This paper proves that for each rational r ∈ [ 2 , 10 / 3 ] , there is a signed series-parallel graph (G , σ) whose circular chromatic number equals r. [ABSTRACT FROM AUTHOR]

Abstract: We characterize all of the ways to represent the wheel matroids and whirl matroids using frame matroids of signed graphs. The characterization of wheels is in terms of topological duality in the projective plane and the characterization of whirls is in terms of topological duality in the annulus. [Copyright &y& Elsevier]

Abstract: We give a decomposition theorem for signed graphs whose frame matroids are binary and a decomposition theorem for signed graphs whose frame matroids are quaternary. [Copyright &y& Elsevier]

Abstract: The isomorphism classes of several types of graph coverings of a graph have been enumerated by many authors [M. Hofmeister, Graph covering projections arising from finite vector space over finite fields, Discrete Math. 143 (1995) 87–97; S. Hong, J.H. Kwak, J.Lee, Regular graph coverings whose covering transformation groups have the isomorphism extention property, Discrete Math. 148 (1996) 85–105; J.H. Kwak, J.H. Chun, J. Lee, Enumeration of regular graph coverings having finite abelian covering transformation groups, SIAM J. Discrete Math. 11 (1998) 273–285; J.H. Kwak, J. Lee, Isomorphism classes of graph bundles, Canad. J. Math. XLII (1990) 747–761; J.H. Kwak, J. Lee, Enumeration of connected graph coverings, J. Graph Theory 23 (1996) 105–109]. Recently, Kwak et al [Balanced regular coverings of a signed graph and regular branched orientable surface coverings over a non-orientable surface, Discrete Math. 275 (2004) 177–193] enumerated the isomorphism classes of balanced regular coverings of a signed graph, as a continuation of an enumeration work done by Archdeacon et al [Bipartite covering graphs, Discrete Math. 214 (2000) 51–63] the isomorphism classes of branched orientable regular surface coverings of a non-orientable surface having a finite abelian covering transformation group. In this paper, we enumerate the isomorphism classes of connected balanced (regular or irregular) coverings of a signed graph and those of unbranched orientable coverings of a non-orientable surface, as an answer of the question raised by Liskovets [Reductive enumeration under mutually orthogonal group actions, Acta-Appl. Math. 52 (1998) 91–120]. As a consequence of these two results, we also enumerate the isomorphism classes of branched orientable surface coverings of a non-orientable surface. [Copyright &y& Elsevier]

Abstract: We prove that a connected cographic matroid of a graph is the bias matroid of a signed graph iff imbeds in the projective plane. In the case that is nonplanar, we also show that must be the projective-planar dual signed graph of an actual imbedding of in the projective plane. As a corollary we get that, if denote the 29 nonseparable forbidden minors for projective-planar graphs, then the cographic matroids of are among the forbidden minors for the class of bias matroids of signed graphs. We will obtain other structural results about bias matroids of signed graphs along the way. [Copyright &y& Elsevier]

The isomorphism classes of several types of graph coverings of a graph have been enumerated by many authors. Kwak and Lee (Canad. J. Math. XLII (1990) 747; J. Graph Theory 23 (1996) 105) enumerated the isomorphism classes of n-fold graph coverings of a graph G. Similar works for regular coverings of a graph can be found in (Discrete Math. 143 (1995) 87; J. Graph Theory 15 (1993) 621; Discrete Math. 148 (1996) 85; Math. Scand. 84 (1999) 23; SIAM J. Discrete Math. 11 (1998) 273). Recently, Archdeacon et al. (Discrete Math. 214 (2000) 51) characterized a bipartite covering of G and enumerated the isomorphism classes of regular 2p-fold bipartite coverings of a non-bipartite graph. As a continuation of their study, we enumerate the isomorphism classes of regular balanced coverings of a signed graph and those of regular bipartite coverings of a graph. Jones (Math. Scand. 84 (1999) 23) enumerated the equivalence classes of the regular branched coverings of any given surface according to the degrees of branch points. This enables us to count the isomorphism classes of the regular branched coverings of a surface. But, it is not easy to derive a counting formula for the isomorphism classes of regular branched orientable surface coverings of a non-orientable surface. As an application of the result, we also enumerate the isomorphism classes of regular branched orientable surface coverings of a non-orientable surface having a finite abelian covering transformation group. It gives a partial answer for the question raised by Liskovets (Acta Appl. Math. 52 (1998) 91). [Copyright &y& Elsevier]

Abstract: We prove that the Petersen colouring conjecture implies a conjecture of Markström saying that the line graph of every bridgeless cubic graph is decomposable into cycles of even length. In addition, we describe two infinite families of 4-regular graphs: the first family consists of 3-connected graphs with no even cycle decomposition and the second one consists of 4-connected signed graphs with no even cycle decomposition. [Copyright &y& Elsevier]

Given a signed graph Σ with n vertices, let μ be an eigenvalue of Σ , and let t be the codimension of the corresponding eigenspace. We prove that n ≤ t + 2 3 whenever μ ∉ { 0 , 1 , − 1 }. We show that this bound is sharp by providing examples of signed graphs in which it is attained. We also discuss particular cases in which the bound can be decreased. [ABSTRACT FROM AUTHOR]

A weighted graph G ω consists of a simple graph G with a weight ω , which is a mapping, ω : E (G) → Z ∖ { 0 }. A signed graph is a graph whose edges are labelled with − 1 or 1. In this paper, we characterize graphs which have a sign such that their signed adjacency matrix has full rank, and graphs which have a weight such that their weighted adjacency matrix does not have full rank. We show that for any arbitrary simple graph G , there is a sign σ so that G σ has full rank if and only if G has a { 1 , 2 } -factor. We also show that for a graph G , there is a weight ω so that G ω does not have full rank if and only if G has at least two { 1 , 2 } -factors. [ABSTRACT FROM AUTHOR]

In this paper, all simple connected signed graphs with maximum degree at most 4 and with just two distinct adjacency eigenvalues are completely characterized, there exists an infinite family of 4-regular signed graphs with just two distinct adjacency eigenvalues. [ABSTRACT FROM AUTHOR]