共查询到20条相似文献,搜索用时 15 毫秒
1.
Jihui Wang Jianfeng Hou Guizhen Liu 《Journal of Applied Mathematics and Computing》2007,24(1-2):357-366
LetG(V, E) be a simple graph, and letf be an integer function onV with 1 ≤f(v) ≤d(v) to each vertexv ∈V. An f-edge cover-coloring of a graphG is a coloring of edge setE such that each color appears at each vertexv ∈V at leastf(v) times. Thef-edge cover chromatic index ofG, denoted by χ′ fc (G), is the maximum number of colors such that anf-edge cover-coloring ofG exists. Any simple graphG has anf-edge cover chromatic index equal to δf or δ f - 1, where $\delta _f = \mathop {\min }\limits_{\upsilon \in V} \{ \left\lfloor {\frac{{d(v)}}{{f(v)}}} \right\rfloor \} $ . LetG be a connected and not complete graph with χ′ fc (G)=δ f-1, if for eachu, v ∈V and e =uv ?E, we have ÷ fc (G + e) > ÷ fc (G), thenG is called anf-edge covered critical graph. In this paper, some properties onf-edge covered critical graph are discussed. It is proved that ifG is anf-edge covered critical graph, then for eachu, v ∈V and e =uv ?E there existsw ∈ {u, v } withd(w) ≤ δ f (f(w) + 1) - 2 such thatw is adjacent to at leastd(w) - δ f + 1 vertices which are all δ f -vertex inG. 相似文献
2.
A. K. Kelmans 《Acta Mathematica Hungarica》1981,37(1-3):77-88
3.
Aequationes mathematicae - For a set $$mathcal {H}$$ of connected graphs, a spanning subgraph H of G is called an $$mathcal {H}$$ -factor of G if each component of H is isomorphic to an element... 相似文献
4.
A graph is matching-covered if every edge of is contained in a perfect matching. A matching-covered graph is strongly coverable if, for any edge of , the subgraph is still matching-covered. An edge subset of a matching-covered graph is feasible if there exist two perfect matchings and such that , and an edge subset with at least two edges is an equivalent set if a perfect matching of contains either all edges in or none of them. A strongly matchable graph does not have an equivalent set, and any two independent edges of form a feasible set. In this paper, we show that for every integer , there exist infinitely many -regular graphs of class 1 with an arbitrarily large equivalent set that is not switching-equivalent to either or , which provides a negative answer to a problem of Lukot’ka and Rollová. For a matching-covered bipartite graph , we show that has an equivalent set if and only if it has a 2-edge-cut that separates into two balanced subgraphs, and is strongly coverable if and only if every edge-cut separating into two balanced subgraphs and satisfies and . 相似文献
5.
In this paper we discuss some basic properties of k-list critical graphs. A graph G is k-list critical if there exists a list assignment L for G with |L(v)|=k−1 for all vertices v of G such that every proper subgraph of G is L-colorable, but G itself is not L-colorable. This generalizes the usual definition of a k-chromatic critical graph, where L(v)={1,…,k−1} for all vertices v of G. While the investigation of k-critical graphs is a well established part of coloring theory, not much is known about k-list critical graphs. Several unexpected phenomena occur, for instance a k-list critical graph may contain another one as a proper induced subgraph, with the same value of k. We also show that, for all 2≤p≤k, there is a minimal k-list critical graph with chromatic number p. Furthermore, we discuss the question, for which values of k and n is the complete graph Knk-list critical. While this is the case for all 5≤k≤n, Kn is not 4-list critical if n is large. 相似文献
6.
7.
A graph G is diameter k-critical if the graph has diameter k and the deletion of any edge increases its diameter. We show that every diameter 2-critical graph on v vertices has (i) at most 0.27v2 edges, and (ii) average edge degree at most v. We also make a conjecture on the maximal number of edges in a diameter k-critical graph. 相似文献
8.
It is shown that the minimal number of edges which have to be omitted from a (k + 1)-critical graph on n vertices in order to make it bipartite is at least k2 for n large enough. This bound is best possible. Various related questions are considered. 相似文献
9.
Jaroslav NešetŘil 《Archiv der Mathematik》1972,23(1):210-213
10.
A dominating set of a graph G=(V,E) is a subset S⊆V such that every vertex not in S is adjacent to at least one vertex of S. The domination number of G is the cardinality of a smallest dominating set. The global domination number, γg(G), is the cardinality of a smallest set S that is simultaneously a dominating set of both G and its complement . Graphs for which γg(G−e)>γg(G) for all edges e∈E are characterized, as are graphs for which γg(G−e)<γg(G) for all edges e∈E whenever is disconnected. Progress is reported in the latter case when is connected. 相似文献
11.
We introduce some determinantal ideals of the generalized Laplacian matrix associated to a digraph G, that we call critical ideals of G. Critical ideals generalize the critical group and the characteristic polynomials of the adjacency and Laplacian matrices of a digraph. The main results of this article are the determination of some minimal generator sets and the reduced Gröbner basis for the critical ideals of the complete graphs, the cycles and the paths. Also, we establish a bound between the number of trivial critical ideals and the stability and clique numbers of a graph. 相似文献
12.
Let P(G,λ) be the chromatic polynomial of a graph G. Two graphs G and H are said to be chromatically equivalent, denoted G~H, if P(G,λ)=P (H,λ). We write [G]={H|H~G}. If[G]={G}, then G is said to be chromatically unique. In this paper, we first characterize certain complete 6-partite graphs with 6n+1 vertices according to the number of 7-independent partitions of G. Using these results, we investigate the chromaticity of G with certain star or matching deleted. As a by-product, many new families of chromatically unique complete 6-partite graphs with certain star or matching deleted are obtained. 相似文献
13.
Ivan Tafteberg Jakobsen 《Discrete Mathematics》1974,9(3):265-276
It is shown that the number of vertices of valency 2 in a critical graph with chromatic index 4 is at most 1/3 of the total number of vertices, and that there exist critical graphs with just one vertex of valency 2, but none with exactly two vertices of valency 2. From this bounds for the number of edges are deduced. The paper ends with a presentation of a catalogue of all critical graphs with chromatic index 4 and at most 8 vertices, and all simple critical graphs with chromatic index 4 and at most 10 vertices. 相似文献
14.
It is well known to us that a graph of diameter has at least eigenvalues. A graph is said to be Laplacian (resp, normalized Laplacian) ‐extremal if it is of diameter having exactly distinct Laplacian (resp, normalized Laplacian) eigenvalues. A graph is split if its vertex set can be partitioned into a clique and a stable set. Each split graph is of diameter at most 3. In this paper, we completely classify the connected bidegreed Laplacian (resp, normalized Laplacian) 2‐extremal (resp, 3‐extremal) split graphs using the association of split graphs with combinatorial designs. Furthermore, we identify connected bidegreed split graphs of diameter 2 having just four Laplacian (resp, normalized Laplacian) eigenvalues. 相似文献
15.
K. Kayathri 《Graphs and Combinatorics》1994,10(2-4):139-144
A conjecture of V.G. Vizing states that if G is a Δ-critical graph of order ? and size m, thenm ≥ 1/2(n(Δ - 1) + 3). This conjecture has been verified for Δ ≤ 4 by I.T. Jakobsen, L.W. Beineke, S. Fiorini and H.P. Yap. In this paper, we prove the conjecture for Δ = 5. 相似文献
16.
17.
《Journal of Combinatorial Theory, Series B》1987,43(3):360-363
Let G be a graph with m edges and n vertices. We show that if 2m−k>n! or if 2m>(2n) + k then G is determined by its collection of k-edge deleted subgraphs. 相似文献
18.
19.
Let G be a multigraph with edge set E(G). An edge coloring C of G is called an edge covered coloring, if each color appears at least once at each vertex v∈V(G). The maximum positive integer k such that G has a k edge covered coloring is called the edge covered chromatic index of G and is denoted by . A graph G is said to be of class if and otherwise of class. A pair of vertices {u,v} is said to be critical if . A graph G is said to be edge covered critical if it is of class and every edge with vertices in V(G) not belonging to E(G) is critical. Some properties about edge covered critical graphs are considered. 相似文献