共查询到20条相似文献,搜索用时 46 毫秒
1.
Partitioning complete graphs by heterochromatic trees 总被引:1,自引:0,他引:1
A heterochromatic tree is an edge-colored tree in which any two edges have different colors. The heterochromatic tree partition number of an r-edge-colored graph G, denoted by t r (G), is the minimum positive integer p such that whenever the edges of the graph G are colored with r colors, the vertices of G can be covered by at most p vertex-disjoint heterochromatic trees. In this paper we determine the heterochromatic tree partition number of r-edge-colored complete graphs. We also find at most t r (K n ) vertex-disjoint heterochromatic trees to cover all the vertices in polynomial time for a given r-edge-coloring of K n . 相似文献
2.
A Necessary and Sufficient Condition for the Existence of a Heterochromatic Spanning Tree in a Graph
Kazuhiro Suzuki 《Graphs and Combinatorics》2006,22(2):261-269
We prove the following theorem. An edge-colored (not necessary to be proper) connected graph G of order n has a heterochromatic spanning tree if and only if for any r colors (1≤r≤n−2), the removal of all the edges colored with these r colors from G results in a graph having at most r+1 components, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors. 相似文献
3.
T. Bartnicki 《Discrete Mathematics》2008,308(8):1388-1393
Using a fixed set of colors C, Ann and Ben color the edges of a graph G so that no monochromatic cycle may appear. Ann wins if all edges of G have been colored, while Ben wins if completing a coloring is not possible. The minimum size of C for which Ann has a winning strategy is called the game arboricity of G, denoted by Ag(G). We prove that Ag(G)?3k for any graph G of arboricity k, and that there are graphs such that Ag(G)?2k-2. The upper bound is achieved by a suitable version of the activation strategy, used earlier for the vertex coloring game. We also provide two other strategies based on induction and acyclic colorings. 相似文献
4.
Let G be an edge-colored graph. The monochromatic tree partition problem is to find the minimum number of vertex disjoint monochromatic
trees to cover the all vertices of G. In the authors’ previous work, it has been proved that the problem is NP-complete and there does not exist any constant
factor approximation algorithm for it unless P = NP. In this paper the authors show that for any fixed integer r ≥ 5, if the edges of a graph G are colored by r colors, called an r-edge-colored graph, the problem remains NP-complete. Similar result holds for the monochromatic path (cycle) partition problem.
Therefore, to find some classes of interesting graphs for which the problem can be solved in polynomial time seems interesting.
A linear time algorithm for the monochromatic path partition problem for edge-colored trees is given.
Supported by the National Natural Science Foundation of China, PCSIRT and the “973” Program. 相似文献
5.
Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal. 相似文献
6.
In this paper we study graphs all of whose star sets induce cliques or co-cliques. We show that the star sets of every tree for each eigenvalue are independent sets. Among other results it is shown that each star set of a connected graph G with three distinct eigenvalues induces a clique if and only if G=K1,2 or K2,…,2. It is also proved that stars are the only graphs with three distinct eigenvalues having a star partition with independent star sets. 相似文献
7.
Let G be an edge-colored graph. A heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d c (v), named the color degree of a vertex v, be defined as the maximum number of edges incident with v, that have distinct colors. In this paper, we prove that if G is an edge-colored triangle-free graph of order n ≥?9 and ${d^c(v) \geq \frac{(3-\sqrt{5})n}{2}+1}$ for each vertex v of G, G has a heterochromatic C 4. 相似文献
8.
9.
An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] conjectured that if G is an r-regular graph and ρ(G)?1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers. 相似文献
10.
Let G be a graph and for any natural number r, denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, . Here we generalize this result and show that . Moreover, we show that if for any two vertices u and v with maximum degree d(u,v)?3, then . Also for any tree T with Δ(T)?3 we prove that . Finally, it is shown that for any graph G with no isolated edges, . 相似文献
11.
Given a graph and an edge coloring C of G, a heterochromatic cycle of G is a cycle in which any pair of edges have distinct colors. Let d c (v), named the color degree of a vertex v, be the maximum number of distinct colored edges incident with v. In this paper, we give several sufficient conditions for the existence of heterochromatic cycles in edge-colored graphs. 相似文献
12.
Oscar Rojo 《Linear algebra and its applications》2008,428(4):754-764
Let G=(V(G),E(G)) be a unicyclic simple undirected graph with largest vertex degree Δ. Let Cr be the unique cycle of G. The graph G-E(Cr) is a forest of r rooted trees T1,T2,…,Tr with root vertices v1,v2,…,vr, respectively. Let
13.
Let G be a family of graphs whose edges are colored with elements from a set R of r colors. We assume no two vertices of G are joined by more than one edge of color i for any i∈R, for each G∈G. will denote the complete graph with r edges joining any pair of distinct vertices, one of each of the r colors. We describe necessary and asymptotically sufficient conditions on n for the existence of a family D of subgraphs of , each of which is an isomorphic copy of some graph in G, so that each edge of appears in exactly one of the subgraphs in D. 相似文献
14.
Wang Qin 《Discrete Mathematics》2005,294(3):303-309
A graph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. A graph G is claw-free, if G does not contain any induced subgraph isomorphic to K1,3. The kth power of a graph G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. In this paper, the 4-regular claw-free IM-extendable graphs are characterized. It is shown that the only 4-regular claw-free connected IM-extendable graphs are , and Tr, r?2, where Tr is the graph with 4r vertices ui,vi,xi,yi, 1?i?r, such that for each i with 1?i?r, {ui,vi,xi,yi} is a clique of Tr and . We also show that a 4-regular strongly IM-extendable graph must be claw-free. As a consequence, the only 4-regular strongly IM-extendable graphs are K4×K2, and . 相似文献
15.
Ting-Chung Chang 《Linear algebra and its applications》2011,435(10):2451-2461
By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then Hn,k, the graph obtained from the star K1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges. 相似文献
16.
Elizabeth C.M. Maritz 《Quaestiones Mathematicae》2018,41(1):49-63
Let Π = {S1, S2, . . . , Sk} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S1), d(v, S2), . . . , d(v, Sk)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(Cn(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators. 相似文献
17.
Pavel Híc 《Discrete Mathematics》2008,308(16):3704-3705
A graph G is called integral if all the roots of the characteristic polynomial P(G;x) are integers. In the paper the first known integral complete 4-partite graph Kp1,p2,p3,p4, where p1<p2<p3<p4, is constructed. 相似文献
18.
Colorings and orientations of graphs 总被引:10,自引:0,他引:10
Bounds for the chromatic number and for some related parameters of a graph are obtained by applying algebraic techniques. In particular, the following result is proved: IfG is a directed graph with maximum outdegreed, and if the number of Eulerian subgraphs ofG with an even number of edges differs from the number of Eulerian subgraphs with an odd number of edges then for any assignment of a setS(v) ofd+1 colors for each vertexv ofG there is a legal vertex-coloring ofG assigning to each vertexv a color fromS(v).Research supported in part by a United States-Israel BSF Grant and by a Bergmann Memorial Grant. 相似文献
19.
A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total
coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k. 相似文献
20.
Linda Eroh 《Discrete Mathematics》2008,308(18):4212-4220
Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by dG(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, dH(S)=dG(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed. 相似文献