共查询到20条相似文献,搜索用时 15 毫秒
1.
In our earlier paper [9], generalizing the well known notion of graceful graphs, a (p, m, n)-signed graph S of order p, with m positive edges and n negative edges, is called graceful if there exists an injective function f that assigns to its p vertices integers 0, 1,...,q = m + n such that when to each edge uv of S one assigns the absolute difference |f(u)-f(v)| the set of integers received by the positive edges of S is {1,2,...,m} and the set of integers received by the negative edges of S is {1,2,...,n}. Considering the conjecture therein that all signed cycles Zk, of admissible length k 3 and signed structures, are graceful, we establish in this paper its truth for all possible signed cycles of lengths 0, 2 or 3 (mod 4) in which the set of negative edges forms a connected subsigraph. 相似文献
2.
3.
4.
《Journal of Graph Theory》2018,87(2):135-148
Let ( be two positive integers. We generalize the well‐studied notions of ‐colorings and of the circular chromatic number to signed graphs. This implies a new notion of colorings of signed graphs, and the corresponding chromatic number χ. Some basic facts on circular colorings of signed graphs and on the circular chromatic number are proved, and differences to the results on unsigned graphs are analyzed. In particular, we show that the difference between the circular chromatic number and the chromatic number of a signed graph is at most 1. Indeed, there are signed graphs where the difference is 1. On the other hand, for a signed graph on n vertices, if the difference is smaller than 1, then there exists , such that the difference is at most . We also show that the notion of ‐colorings is equivalent to r‐colorings (see [12] (X. Zhu, Recent developments in circular coloring of graphs, in Topics in Discrete Mathematics Algorithms and Combinatorics Volume 26 , Springer Berlin Heidelberg, 2006, pp. 497–550)). 相似文献
5.
The key to Seymour's Regular Matroid Decomposition Theorem is his result that each 3‐connected regular matroid with no R10‐ or R12‐minor is graphic or cographic. We present a proof of this in terms of signed graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 74–84, 2005 相似文献
6.
Signed graphs for portfolio analysis in risk management 总被引:1,自引:0,他引:1
Harary Frank; Lim Meng-Hiot; Wunsch Donald C. 《IMA Journal of Management Mathematics》2002,13(3):201-210
We introduce the notion of structural balance for signed graphsin the context of portfolio analysis. A portfolio of securitiescan be represented as a signed graph with the nodes denotingthe securities and the edges representing the correlation betweenthe securities. With signed graphs, the characteristics of aportfolio from a risk management perspective can be uncoveredfor analysis purposes. It is shown that a portfolio characterizedby a signed graph of positive and negative edges that is structurallybalanced is characteristically more predictable. Investors whoundertake a portfolio position with all positively correlatedsecurities do so with the intention to speculate on the upside(or downside). If the portfolio consists of negative edges andis balanced, then it is likely that the position has a hedgingdisposition within it. On the other hand, an unbalanced signedgraph is representative of an investment portfolio which ischaracteristically unpredictable. 相似文献
7.
8.
A signed circuit is a minimal signed graph (with respect to inclusion) that admits a nowhere-zero flow. We show that each flow-admissible signed graph on edges can be covered by signed circuits of total length at most , improving a recent result of Cheng et al. To obtain this improvement, we prove several results on signed circuit covers of trees of Eulerian graphs, which are connected signed graphs such that removing all bridges results in a collection of Eulerian graphs. 相似文献
9.
The signed distance-k-domination number of a graph is a certain variant of the signed domination number. If v is a vertex of a graph G, the open k-neighborhood of v, denoted by N
k
(v), is the set N
k
(v) = {u: u ≠ v and d(u, v) ⩽ k}. N
k
[v] = N
k
(v) ⋃ {v} is the closed k-neighborhood of v. A function f: V → {−1, 1} is a signed distance-k-dominating function of G, if for every vertex
. The signed distance-k-domination number, denoted by γ
k,s
(G), is the minimum weight of a signed distance-k-dominating function on G. The values of γ
2,s
(G) are found for graphs with small diameter, paths, circuits. At the end it is proved that γ
2,s
(T) is not bounded from below in general for any tree T. 相似文献
10.
11.
As shown in [D. Hoffman, H. Jordon, Signed graph factors and degree sequences, J. Graph Theory 52 (2006) 27-36], the degree sequences of signed graphs can be characterized by a system of linear inequalities. The set of all n-tuples satisfying this system of linear inequalities is a polytope Pn. In this paper, we show that Pn is the convex hull of the set of degree sequences of signed graphs of order n. We also determine many properties of Pn, including a characterization of its vertices. The convex hull of imbalance sequences of digraphs is also investigated using the characterization given in [D. Mubayi, T.G. Will, D.B. West, Realizing degree imbalances of directed graphs, Discrete Math. 239 (2001) 147-153]. 相似文献
12.
On signed majority total domination in graphs 总被引:1,自引:0,他引:1
We initiate the study of signed majority total domination in graphs. Let G = (V, E) be a simple graph. For any real valued function f: V and S
V, let
. A signed majority total dominating function is a function f: V {–1, 1} such that f(N(v)) 1 for at least a half of the vertices v V. The signed majority total domination number of a graph G is
= min{f(V): f is a signed majority total dominating function on G}. We research some properties of the signed majority total domination number of a graph G and obtain a few lower bounds of
.This research was supported by National Natural Science Foundation of China. 相似文献
13.
14.
For a signed graph G and function , a signed f‐factor of G is a spanning subgraph F such that sdegF(υ) = f(υ) for every vertex υ of G, where sdeg(υ) is the number of positive edges incident with v less the number of negative edges incident with υ, with loops counting twice in either case. For a given vertex‐function f, we provide necessary and sufficient conditions for a signed graph G to have a signed f‐factor. As a consequence of this result, an Erd?s‐Gallai‐type result is given for a sequence of integers to be the degree sequence of a signed r‐graph, the graph with at most r positive and r negative edges between a given pair of distinct vertices. We discuss how the theory can be altered when mixed edges (i.e., edges with one positive and one negative end) are allowed, and how it applies to bidirected graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 27–36, 2006 相似文献
15.
T. S. Michael 《Journal of Graph Theory》2002,41(2):101-105
We give necessary and sufficient conditions for the existence of a signed r‐multigraph with a prescribed signed degree sequence. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 101–105, 2002 相似文献
16.
17.
18.
H. Karami S. M. Sheikholeslami Abdollah Khodkar 《Czechoslovak Mathematical Journal》2008,58(3):595-603
The open neighborhood N
G
(e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ
st
′(G). Obviously, γ
st
′(G) is defined only for graphs G which have no connected components isomorphic to K
2. In this paper we present some lower bounds for γ
st
′(G). In particular, we prove that γ
st
′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ
st
′(T).
Research supported by a Faculty Research Grant, University of West Georgia. 相似文献
19.
特殊图类的符号控制数 总被引:2,自引:1,他引:1
王军秀 《纯粹数学与应用数学》2005,21(1):59-61
图G的符号控制数γS(G)有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其上下界有重要意义.本文研究了1)一般图G的符号控制数,给出了一个新的下界;2)确定了Cn图的符号控制数的精确值. 相似文献
20.
Bohdan Zelinka 《Czechoslovak Mathematical Journal》2005,55(2):479-482
The concept of signed domination number of an undirected graph (introduced by J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and P. J. Slater) is transferred to directed graphs. Exact values are found for particular types of tournaments. It is proved that for digraphs with a directed Hamiltonian cycle the signed domination number may be arbitrarily small. 相似文献