共查询到20条相似文献,搜索用时 15 毫秒
1.
《Discrete Mathematics》2019,342(1):233-249
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 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 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 and type . In this paper, we give a characterization of the freeness and supersolvability of the Weyl subarrangements of type under certain assumption. 相似文献
2.
A signed graph has a plus or minus sign on each edge. A simple cycle is positive or negative depending on whether it contains an even or odd number of negative edges, respectively. We consider embeddings of a signed graph in the projective plane for which a simple cycle is essential if and only if it is negative. We characterize those signed graphs that have such a projective-planar embedding. Our characterization is in terms of a related signed graph formed by considering the theta subgraphs in the given graph. 相似文献
3.
4.
The circular flow number Φc(G,σ) of a signed graph (G,σ) is the minimum r for which an orientation of (G,σ) admits a circular r-flow. We prove that the circular flow number of a signed graph (G,σ) is equal to the minimum imbalance ratio of an orientation of (G,σ). We then use this result to prove that if G is 4-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) (as well as Φ(G,σ)) is at most 4. If G is 6-edge-connected and (G,σ) has a nowhere zero flow, then Φc(G,σ) is strictly less than 4. 相似文献
5.
6.
On signed cycle domination in graphs 总被引:2,自引:0,他引:2
Baogen Xu 《Discrete Mathematics》2009,309(4):1007-1387
Let G=(V,E) be a graph, a function f:E→{−1,1} is said to be an signed cycle dominating function (SCDF) of G if ∑e∈E(C)f(e)≥1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as is an SCDF of G}. In this paper, we obtain bounds on , characterize all connected graphs G with , and determine the exact value of for some special classes of graphs G. In addition, we pose some open problems and conjectures. 相似文献
7.
《Discrete Mathematics》2019,342(12):111615
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. 相似文献
8.
9.
A simple algorithm to detect balance in signed graphs 总被引:1,自引:0,他引:1
We develop a natural correspondence between marked graphs and balanced signed graphs, and exploit it to obtain a simple linear time algorithm by which any signed graph may be tested for balance. 相似文献
10.
Let G be a finite and simple graph with vertex set V(G), and let f:V(G)→{−1,1} be a two-valued function. If ∑x∈N[v]f(x)≥1 for each v∈V(G), where N[v] is the closed neighborhood of v, then f is a signed dominating function on G. A set {f1,f2,…,fd} of signed dominating functions on G with the property that for each x∈V(G), is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number on G. In this paper, we investigate the signed domatic number of some circulant graphs and of the torus Cp×Cq. 相似文献
11.
12.
A numerical invariant of directed graphs concerning domination which is named signed domination number γS is studied in this paper. We present some sharp lower bounds for γS in terms of the order, the maximum degree and the chromatic number of a directed graph. 相似文献
13.
14.
We view an undirected graph as a symmetric digraph, where each edge is replaced by two opposite arcs and . Assume is an inverse closed subset of permutations of positive integers. We say is --colourable if for any mapping with , there is a mapping such that for each arc . The concept of --colourable is a common generalization of several other colouring concepts. This paper is focused on finding the sets such that every triangle-free planar graph is -3-colourable. Such a set is called TFP-good. Grötzsch’s theorem is equivalent to say that is TFP-good. We prove that for any inverse closed subset of which is not isomorphic to , is TFP-good if and only if either or there exists such that for each , . It remains an open question to determine whether or not is TFP-good. 相似文献
15.
Kumar and Madhavan [Minimal vertex separators of chordal graphs, Discrete Appl. Math. 89 (1998) 155-168] gave a linear time algorithm to list all the minimal separators of a chordal graph. In this paper we give another linear time algorithm for the same purpose. While the algorithm of Kumar and Madhavan requires that a specific type of PEO, namely the MCS PEO is computed first, our algorithm works with any PEO. This is interesting when we consider the fact that there are other popular methods such as Lex BFS to compute a PEO for a given chordal graph. 相似文献
16.
D.R. Shier 《Discrete Applied Mathematics》1984,7(3):325-331
This paper studies properties of perfect elimination orderings in chordal graphs. Specific connections to convex subsets and quasiconcave functions in a graph are discussed. Several new schemes for generating all perfect elimination orderings are investigated and related to existing schemes. 相似文献
17.
18.
《Discrete Mathematics》2022,345(8):112917
Let and denote the flow number and the circular flow number of a flow-admissible signed graph , respectively. It is known that for every unsigned graph G. Based on this fact, in 2011 Raspaud and Zhu conjectured that holds also for every flow-admissible signed graph . 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 if and only if and if , then . 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. 相似文献
19.
20.
Mostafa Blidia 《Discrete Mathematics》2008,308(10):1785-1791
We examine classes of extremal graphs for the inequality γ(G)?|V|-max{d(v)+βv(G)}, where γ(G) is the domination number of graph G, d(v) is the degree of vertex v, and βv(G) is the size of a largest matching in the subgraph of G induced by the non-neighbours of v. This inequality improves on the classical upper bound |V|-maxd(v) due to Claude Berge. We give a characterization of the bipartite graphs and of the chordal graphs that achieve equality in the inequality. The characterization implies that the extremal bipartite graphs can be recognized in polynomial time, while the corresponding problem remains NP-complete for the extremal chordal graphs. 相似文献