共查询到20条相似文献,搜索用时 0 毫秒
1.
Martin Milanič 《Journal of Graph Theory》2013,73(4):400-424
An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the graph's vertex set. We introduce graphs that are hereditary efficiently dominatable in that sense that every induced subgraph of the graph contains an efficient dominating set. We prove a decomposition theorem for (bull, fork, C4)‐free graphs, based on which we characterize, in terms of forbidden induced subgraphs, the class of hereditary efficiently dominatable graphs. We also give a decomposition theorem for hereditary efficiently dominatable graphs and examine some algorithmic aspects of such graphs. In particular, we give a polynomial time algorithm for finding an efficient dominating set (if one exists) in a class of graphs properly containing the class of hereditary efficiently dominatable graphs by reducing the problem to the maximum weight independent set problem in claw‐free graphs. 相似文献
2.
3.
Mark Ginn 《Journal of Graph Theory》1999,30(2):71-76
We show that the minimum set of unordered graphs that must be forbidden to get the same graph class characterized by forbidding a single ordered graph is infinite. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 71–76, 1999 相似文献
4.
CHENHUAITANG MAKEJIE 《高校应用数学学报(英文版)》1998,13(2):165-170
The definition of the ascending suhgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition. 相似文献
5.
6.
研究子图的度和图的哈密尔顿性的关系,证明图~$G$ 是一个~$n$ 阶~3-\,连通无爪图且最小度~$\delta(G)\geq4$, 如果图~$G$ 中任意两个分别同构于~$P_4$, $K_1$ 的不相邻子图~$H_1$, $H_2$ 满足~$d(H_1)+d(H_2)\geq n$, 则图~$G$ 是哈密尔顿连通. 相似文献
7.
Nguyen H. V. Hu'ng 《Transactions of the American Mathematical Society》2001,353(11):4447-4460
Let be Singer's invariant-theoretic model of the dual of the lambda algebra with , where denotes the mod 2 Steenrod algebra. We prove that the inclusion of the Dickson algebra, , into is a chain-level representation of the Lannes-Zarati dual homomorphism
The Lannes-Zarati homomorphisms themselves, , correspond to an associated graded of the Hurewicz map
Based on this result, we discuss some algebraic versions of the classical conjecture on spherical classes, which states that Only Hopf invariant one and Kervaire invariant one classes are detected by the Hurewicz homomorphism. One of these algebraic conjectures predicts that every Dickson element, i.e. element in , of positive degree represents the homology class in for 2$">.
We also show that factors through , where denotes the differential of . Therefore, the problem of determining should be of interest.
8.
For a graph G we define a graph T(G) whose vertices are the triangles in G and two vertices of T(G) are adjacent if their corresponding triangles in G share an edge. Kawarabayashi showed that if G is a k‐connected graph and T(G) contains no edge, then G admits a k‐contractible clique of size at most 3, generalizing an earlier result of Thomassen. In this paper, we further generalize Kawarabayashi's result by showing that if G is k‐connected and the maximum degree of T(G) is at most 1, then G admits a k‐contractible clique of size at most 3 or there exist independent edges e and f of G such that e and f are contained in triangles sharing an edge and G/e/f is k‐connected. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 121–136, 2007 相似文献
9.
Hong-Jian Lai 《Discrete Mathematics》2001,230(1-3):63-69
For an integer l0, define
to be the family of graphs such that
if and only if for any edge subset XE(G) with |X|l, G has a spanning eulerian subgraph H with XE(H). The graphs in
are known as supereulerian graphs. Let f(l) be the minimum value of k such that every k-edge-connected graph is in
. Jaeger and Catlin independently proved f(0)=4. We shall determine f(l) for all values of l0. Another problem concerning the existence of eulerian subgraphs containing given edges is also discussed, and former results in [J. Graph Theory 1 (1977) 79–84] and [J. Graph Theory 3 (1979) 91–93] are extended. 相似文献
10.
Let H be a given graph. A graph G is said to be H‐free if G contains no induced copies of H. For a class of graphs, the graph G is ‐free if G is H‐free for every . Bedrossian characterized all the pairs of connected subgraphs such that every 2‐connected ‐free graph is hamiltonian. Faudree and Gould extended Bedrossian's result by proving the necessity part of the result based on infinite families of non‐hamiltonian graphs. In this article, we characterize all pairs of (not necessarily connected) graphs such that there exists an integer n0 such that every 2‐connected ‐free graph of order at least n0 is hamiltonian. 相似文献
11.
Thomassen recently proved, using the Tutte cycle technique, that if G is a 3-connected cubic triangle-free planar graph then G contains a bipartite subgraph with at least edges, improving the previously known lower bound . We extend Thomassen’s technique and further improve this lower bound to . 相似文献
12.
图模式挖掘中的子图同构算法 总被引:1,自引:0,他引:1
图模式挖掘问题在Web挖掘、生物信息学、社会关系等众多领域有广泛的应用,它涉及到子图的搜索以及子图的同构问题.这两个问题都具有相当高的计算复杂度,现有的子图同构问题大多采用最小编码算法,但对无标签图特别是对无标签无向图,该算法效率较底,从而子图的同构成为图模式挖掘问题的一个瓶颈.针对无标签图,以代数理论为基础,分别利用度序列和特征值构造了两种子图同构算法,用于对有向图和无向图的同构判别.最后对2个真实生物网络进行了仿真实验,结果表明,算法的效率优于现有算法. 相似文献
13.
We combine two well-known results by Mader and Thomassen, respectively. Namely, we prove that for any k-connected graph G (k≥4), there is an induced cycle C such that G−V(C) is (k−3)-connected and G−E(C) is (k−2)-connected. Both “(k−3)-connected” and “(k−2)-connected” are best possible in a sense. 相似文献
14.
Akira Hiraki 《Journal of Algebraic Combinatorics》2001,14(2):127-131
Let be a distance-regular graph of diameter d, valency k and r := maxi | (c
i,b
i) = (c
1,b
1). Let q be an integer with r + 1 q d – 1.In this paper we prove the following results:
Theorem 1
Suppose for any pair of vertices at distance q there exists a strongly closed subgraph of diameter q containing them. Then for any integer i with 1 i q
and for any pair of vertices at distance i there exists a strongly closed subgraph of diameter i containing them.
Theorem 2
If r 2, then
c
2r+3 1.As a corollary of Theorem 2 we have d k
2(r + 1) if r 2. 相似文献
15.
Strongly Closed Subgraphs in a Distance-Regular Graph with <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript> > 1 总被引:1,自引:1,他引:0
Akira Hiraki 《Graphs and Combinatorics》2008,24(6):537-550
Let Γ be a distance-regular graph of diameter d ≥ 3 with c
2 > 1. Let m be an integer with 1 ≤ m ≤ d − 1. We consider the following conditions:
Suppose that the condition (SC)
m
holds. Then it has been known that the condition (BB)
i
holds for all i with 1 ≤ i ≤ m. Similarly we can show that the condition (CA)
i
holds for all i with 1 ≤ i ≤ m. In this paper we prove that if the conditions (BB)
i
and (CA)
i
hold for all i with 1 ≤ i ≤ m, then the condition (SC)
m
holds. Applying this result we give a sufficient condition for the existence of a dual polar graph as a strongly closed subgraph
in Γ. 相似文献
(SC) m : For any pair of vertices at distance m there exists a strongly closed subgraph of diameter m containing them. | |
(BB) m : Let (x, y, z) be a triple of vertices with ∂ Γ (x, y) = 1 and ∂ Γ (x, z) = ∂ Γ (y, z) = m. Then B(x, z) = B(y, z). | |
(CA) m : Let (x, y, z) be a triple of vertices with ∂ Γ (x, y) = 2, ∂ Γ (x, z) = ∂ Γ (y, z) = m and |C(z, x) ∩ C(z, y)| ≥ 2. Then C(x, z) ∪ A(x, z) = C(y, z) ∪ A(y, z). |
16.
Qian Kong 《Discrete Mathematics》2010,310(24):3523-3527
Let Γ denote a distance-regular graph with a strongly closed regular subgraph Y. Hosoya and Suzuki [R. Hosoya, H. Suzuki, Tight distance-regular graphs with respect to subsets, European J. Combin. 28 (2007) 61-74] showed an inequality for the second largest and least eigenvalues of Γ in the case Y is of diameter 2. In this paper, we study the case when Γ is bipartite and Y is of diameter 3, and obtain an inequality for the second largest eigenvalue of Γ. Moreover, we characterize the distance-regular graphs with a completely regular strongly closed subgraph H(3,2). 相似文献
17.
We consider the only remaining unsolved case n≡0 (mod k) for the largest kth eigenvalue of trees with n vertices. In 1995, Jia-yu Shao gave complete solutions for the cases k=2,3,4,5,6 and provided some necessary conditions for extremal trees in general cases (cf. [Linear Algebra Appl. 221 (1995) 131]). We further improve Shao's necessary condition in this paper, which can be seen as the continuation of [Linear Algebra Appl. 221 (1995) 131]. 相似文献
18.
A graph is polar if the vertex set can be partitioned into A and B in such a way that the subgraph induced by A is a complete multipartite graph and the subgraph induced by B is a disjoint union of cliques. Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. However, recognizing polar graphs is an NP-complete problem in general. This led to the study of the polarity of special classes of graphs such as cographs and chordal graphs, cf. Ekim et al. (2008) [7] and [5]. In this paper, we study the polarity of line graphs and call a graph line-polar if its line graph is polar. We characterize line-polar bipartite graphs in terms of forbidden subgraphs. This answers a question raised in the fist reference mentioned above. Our characterization has already been used to develop a linear time algorithm for recognizing line-polar bipartite graphs, cf. Ekim (submitted for publication) [6]. 相似文献
19.
A graph G is perfectly orderable, if it admits an order < on its vertices such that the sequential coloring algorithm delivers an optimum coloring on each induced subgraph (H, <) of (G, <). A graph is a threshold graph, if it contains no P4, 2K2, and C4 as induced subgraph. A theorem of Chvátal, Hoàng, Mahadev, and de Werra states that a graph is perfectly orderable, if it is the union of two threshold graphs. In this article, we investigate possible generalizations of the above theorem. Hoàng has conjectured that, if G is the union of two graphs G1 and G2, then G is perfectly orderable whenever G1 and G2 are both P4‐free and 2K2‐free. We show that the complement of the chordless cycle with at least five vertices cannot be a counter‐example to this conjecture, and we prove a special case of it: if G1 and G2 are two edge‐disjoint graphs that are P4‐free and 2K2‐free, then the union of G1 and G2 is perfectly orderable. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 32–43, 2000 相似文献