共查询到20条相似文献,搜索用时 500 毫秒
1.
Let G=(V,E) be a simple graph. For an edge e of G, the closed edge-neighbourhood of e is the set N[e]={e′∈E|e′ is adjacent to e}∪{e}. A function f:E→{1,−1} is called a signed edge domination function (SEDF) of G if ∑e′∈N[e]f(e′)≥1 for every edge e of G. The signed edge domination number of G is defined as . In this paper, we characterize all trees T with signed edge domination numbers 1, 2, 3, or 4. 相似文献
2.
An edge e of a graph G is said to be a fixed edge if G−e+e
′≅G implies that e
′=e, and a forced edge if G−e+e
′ is an edge-reconstruction of G implies that e
′=e. In this paper, we use the method of excludable configurations to investigate the fixed edges and the forced edges of series-parallel
networks. It is proved that all series-parallel networks contain fixed edges except P
3∨K
1 and P
4∨K
1, and that all series-parallel networks are edge-reconstructible.
Received: December 22, 1997 Final version received: July 21, 1999 相似文献
3.
Let G be a finite graph on the vertex set [d] = {1,…, d} with the edges e 1,…, e n and K[t] = K[t 1,…, t d ] the polynomial ring in d variables over a field K. The edge ring of G is the semigroup ring K[G] which is generated by those monomials t e = t i t j such that e = {i, j} is an edge of G. Let K[x] = K[x 1,…, x n ] be the polynomial ring in n variables over K, and define the surjective homomorphism π: K[x] → K[G] by setting π(x i ) = t e i for i = 1,…, n. The toric ideal I G of G is the kernel of π. It will be proved that, given integers f and d with 6 ≤ f ≤ d, there exists a finite connected nonbipartite graph G on [d] together with a reverse lexicographic order <rev on K[x] and a lexicographic order <lex on K[x] such that (i) K[G] is normal with Krull-dim K[G] = d, (ii) depth K[x]/in<rev (I G ) = f and K[x]/in<lex (I G ) is Cohen–Macaulay, where in<rev (I G ) (resp., in<lex (I G )) is the initial ideal of I G with respect to <rev (resp., <lex) and where depth K[x]/in<rev (I G ) is the depth of K[x]/in<rev (I G ). 相似文献
4.
We introduce a concept of edge-distinguishing colourings of graphs. A closed neighbourhood of an edge \({e\in E(G)}\) is a subgraph N[e] induced by e and all edges adjacent to it. We say that a colouring c : E(G) → C does not distinguish two edges e 1 and e 2 if there exists an isomorphism φ of N[e 1] onto N[e 2] such that φ(e 1) = e 2 and φ preserves colours of c. An edge-distinguishing index of a graph G is the minimum number of colours in a proper colouring which distinguishes every two distinct edges of G. We determine the edge-distinguishing index for cycles, paths and complete graphs. 相似文献
5.
. In this work we consider finite undirected simple graphs. If G=(V,E) is a graph we denote by α(G) the stability number of G. For any vertex x let N[x] be the union of x and the neighborhood N(x). For each pair of vertices ab of G we associate the set J(a,b) as follows. J(a,b)={u∈N[a]∩N[b]∣N(u)⊆N[a]∪N[b]}. Given a graph G, its partially squareG
* is the graph obtained by adding an edge uv for each pair u,v of vertices of G at distance 2 whenever J(u,v) is not empty. In the case G is a claw-free graph, G
* is equal to G
2.
If G is k-connected, we cover the vertices of G by at most ⌈α(G
*)/k⌉ cycles, where α(G
*) is the stability number of the partially square graph of G. On the other hand we consider in G
* conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t≥2). If ∑
x
∈
S
deg
G
(x)≥|G|, for every t-stable set S⊆V(G) of G
* then the vertex set of G can be covered with t−1 cycles. Different corollaries on covering by paths are given.
Received: January 22, 1997 Final version received: February 15, 2000 相似文献
6.
A total coloring of a graph G is a coloring of all elements of G, i.e., vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Let L(x) be a set of colors assigned to each element x of G. Then a list total coloring of G is a total coloring such that each element x receives a color contained in L(x). The list total coloring problem asks whether G has a list total coloring. In this paper, we first show that the list total coloring problem is NP-complete even for series-parallel graphs. We then give a sufficient condition for a series-parallel graph to have a list total coloring, that is, we prove a theorem that any series-parallel graph G has a list total coloring if |L(v)|min{5,Δ+1} for each vertex v and |L(e)|max{5,d(v)+1,d(w)+1} for each edge e=vw, where Δ is the maximum degree of G and d(v) and d(w) are the degrees of the ends v and w of e, respectively. The theorem implies that any series-parallel graph G has a total coloring with Δ+1 colors if Δ4. We finally present a linear-time algorithm to find a list total coloring of a given series-parallel graph G if G satisfies the sufficient condition. 相似文献
7.
Hamiltonism and Partially Square Graphs 总被引:10,自引:0,他引:10
Given a graph G, we define its partially square graph G
* as the graph obtained by adding edges uv whenever the vertices u and v have a common neighbor x satisfying the condition N
G[x]⊆N
G[u]∪N
G [v], where N
G[x]=N
G(x)∪{x}. In particular, this condition is satisfied if x does not center a claw (an induced K
1,3). Obviously G⊆G
*⊆G
2, where G
2 is the square of G. We prove that a k-connected graph (k≥2) G is hamiltonian if the independence number α(G
*) of G
* does not exceed k. If we replace G
* by G we get a well known result of Chvátal and Erdo?s. If G is claw-free and G
* is replaced by G
2 then we obtain a result of Ainouche, Broersma and Veldman. Relationships between connectivity of G and independence number of G
* for other hamiltonian properties are also given in this paper.
Received: June 17, 1996 Revised: October 30, 1998 相似文献
8.
We say that a graph G is quasi claw-free if every pair (a
1, a
2) of vertices at distance 2 satisfies {u∈N (a
1)∩N (a
2) | N[u]⊆N[a
1]∪N [a
2]}≠∅. A cycle C is m-dominating if every vertex of G is of distance at most m from C. We prove that if G is a κ-connected (κ≥2) quasi claw-free graph then either G has an m-dominating cycle or G has a set of at least κ+1 vertices such that the distance between every pair of them is at least 2m+3.
Received: June 12, 1996 Revised: November 9, 1998 相似文献
9.
A dominating set D ⊆ V(G) is a weakly connected dominating set in G if the subgraph G[D]
w
= (N
G
[D], E
w
) weakly induced by D is connected, where E
w
is the set of all edges having at least one vertex in D. Weakly connected domination number
γw
(G) of a graph G is the minimum cardinality among all weakly connected dominating sets in G. A graph G is said to be weakly connected domination stable or just
γw
-stable if
γw
(G) =
γ w
(G + e) for every edge e belonging to the complement Ḡ of G. We provide a constructive characterization of weakly connected domination stable trees.
相似文献
10.
The Linear Arboricity of Series-Parallel Graphs 总被引:8,自引:0,他引:8
Jianliang Wu 《Graphs and Combinatorics》2000,16(3):367-372
The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. A graph is called series-parallel if it contains no subgraphs homeomorphic to K
4. In this paper, we prove that for any series-parallel graph G having Δ (G)≥3. Since an outerplanar graph is a series-parallel graph, this is also true for any outerplanar graph.
Received: August 20, 1997 Revised: March 12, 1999 相似文献
11.
LetG=(V, E) be an undirected graph andc any vector in ℤ
V(G)
+. Denote byχ(G
c) (resp.η(G
c)) the chromatic number (resp. fractional chromatic number) ofG with respect toc. We study graphs for whichχ(G
c)−[η(G
c)]⩽1. We show that for the class of graphs satisfyingχ(G
c)=[η(G
c)] (a class generalizing perfect graphs), an analogue of the Duplication Lemma does not hold. We also describe a 2-vertex
cut decomposition procedure related to the integer decomposition property. We use this procedure to show thatχ(G
c)=[η(G
c)] for series-parallel graphs andχ(G
c)⩽[η(G
c)]+1 for graphs that do not have the 4-wheel as a minor.
The work of this author was supported by the Natural Sciences and Engineering Research Council of Canada (NSERCC) under grant
A9126. 相似文献
12.
Giuseppe Molteni 《Archiv der Mathematik》2002,79(6):432-438
We prove that a functionF of the Selberg class ℐ is ab-th power in ℐ, i.e.,F=H
b for someHσ ℐ, if and only ifb divides the order of every zero ofF and of everyp-componentF
p. This implies that the equationF
a=Gb with (a, b)=1 has the unique solutionF=H
b andG=H
a in ℐ. As a consequence, we prove that ifF andG are distinct primitive elements of ℐ, then the transcendence degree of ℂ[F,G] over ℂ is two. 相似文献
13.
Let G be an undirected simple connected graph, and e = uv be an edge of G. Let N
G(e) be the subgraph of G induced by the set of all vertices of G which are not incident to e but are adjacent to u or v. Let N
e be the class of all graphs H such that, for some graph G,N
G
(e) H for every edge e of G. Zelinka [3] studied edge neighborhood graphs and obtained some special graphs in N
e. Balasubramanian and Alsardary [1] obtained some other graphs in N
e. In this paper we given some new graphs in N
e. 相似文献
14.
Xuding Zhu 《Journal of Graph Theory》2005,48(3):186-209
For 1 ≤ d ≤ k, let Kk/d be the graph with vertices 0, 1, …, k ? 1, in which i ~j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χc(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to Kk/d. The circular clique number ωc(G) of G is the maximum of those k/d for which Kk/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χc(H) = ωc(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, NG[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, NG[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P5 (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph Kk/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005 相似文献
15.
The closed neighborhood NG[e] of an edge e in a graph G is the set consisting of e and of all edges having an end-vertex in common 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 dominating function of G. The signed edge domination number γs′(G) of G is defined as
. Recently, Xu proved that γs′(G) ≥ |V(G)| − |E(G)| for all graphs G without isolated vertices. In this paper we first characterize all simple connected graphs G for which γs′(G) = |V(G)| − |E(G)|. This answers Problem 4.2 of [4]. Then we classify all simple connected graphs G with precisely k cycles and γs′(G) = 1 − k, 2 − k.
A. Khodkar: Research supported by a Faculty Research Grant, University of West Georgia.
Send offprint requests to: Abdollah Khodkar. 相似文献
16.
Let G be a finite simple graph. Let S⊆V(G), its closed interval I[S] is the set of all vertices lying on shortest paths between any pair of vertices of S. The set S is convex if I[S]=S. In this work we define the concept of a convex partition of graphs. If there exists a partition of V(G) into p convex sets we say that G is p-convex. We prove that it is NP-complete to decide whether a graph G is p-convex for a fixed integer p≥2. We show that every connected chordal graph is p-convex, for 1≤p≤n. We also establish conditions on n and k to decide if the k-th power of a cycle Cn is p-convex. Finally, we develop a linear-time algorithm to decide if a cograph is p-convex. 相似文献
17.
A graph G is (2, 1)-colorable if its vertices can be partitioned into subsets V
1 and V
2 such that each component in G[V
1] contains at most two vertices while G[V
2] is edgeless. We prove that every graph with maximum average degree mad(G) < 7/3 is (2, 1)-colorable. It follows that every planar graph with girth at least 14 is (2, 1)-colorable. We also construct
a planar graph G
n
with mad (G
n
) = (18n − 2)/(7n − 1) that is not (2, 1)-colorable. 相似文献
18.
Katarzyna Jesse-Józefczyk 《Central European Journal of Mathematics》2012,10(3):1113-1124
Let G = (V, E) be a graph. A global secure set SD ⊆ V is a dominating set which satisfies the condition: for all X ⊆ SD, |N[X] ∩ SD| ≥ | N[X] − SD|. A global defensive alliance is a set of vertices A that is dominating and satisfies a weakened condition: for all x ∈ A, |N[x] ∩ A| ≥ |N[x] − A|. We give an upper bound on the cardinality of minimum global secure sets in cactus trees. We also present some results for
trees, and we relate them to the known bounds on the minimum cardinality of global defensive alliances. 相似文献
19.
Mordechai Katzman 《Journal of Algebra》1999,220(2):3111
Let R be a monomial subalgebra of k[x1,…,xN] generated by square free monomials of degree two. This paper addresses the following question: when is R a complete intersection? For such a k-algebra we can associate a graph G whose vertices are x1,…,xN and whose edges are {(xi, xj)|xixj R}. Conversely, for any graph G with vertices {x1,…,xN} we define the edge algebra associated with G as the subalgebra of k[x1,…,xN] generated by the monomials {xixj|(xi, xj) is an edge of G}. We denote this monomial algebra by k[G]. This paper describes all bipartite graphs whose edge algebras are complete intersections. 相似文献
20.
Burcu Baran 《Archiv der Mathematik》2010,94(1):11-18
Let p be a prime number and G be a finite commutative group such that p
2 does not divide the order of G. In this note we prove that for every finite module M over the group ring Z
p
[G], the inequality #M £ #Zp[G]/FitZp[G](M){\#M\,\leq\,\#{\bf Z}_{p}[G]/{{\rm Fit}}_{{\bf Z}_{p}[G]}(M)} holds. Here, FitZp[G](M){\rm Fit}_{{\bf Z}_{p}[G]}(M) is the Z
p
[G]-Fitting ideal of M. 相似文献