共查询到20条相似文献,搜索用时 15 毫秒
1.
A kernel of a directed graph is a set of vertices K that is both absorbant and independent (i.e., every vertex not in K is the origin of an arc whose extremity is in K, and no arc of the graph has both endpoints in K). In 1983, Meyniel conjectured that any perfect graph, directed in such a way that every circuit of length three uses two reversible arcs, must have a kernel. This conjecture was proved for parity graphs. In this paper, we extend that result and prove that Meyniel's conjecture holds for all graphs in which every odd cycle has two chords. 相似文献
3.
An antimagic labeling of a digraph with vertices and arcs is a bijection from the set of arcs of to such that all oriented vertex sums are pairwise distinct, where an oriented vertex sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. Hefetz, Mütze and Schwartz conjectured every connected undirected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that every Halin graph admits an antimagic orientation. 相似文献
4.
An identity orientation of a graph G=(V,E) is an orientation of some of the edges of E such that the resulting partially oriented graph has no automorphism other than the identity. We show that the complete bipartite graph Ks,t, with st, does not have an identity orientation if t3s-log3(s-1). We also show that if (r+1)(r+2)2s then Ks,3s-r does have an identity orientation. These results improve the previous bounds obtained by Harary and Jacobson (Discuss. Math. - Graph Theory 21 (2001) 158). We use these results to determine exactly the values of t for which an identity orientation of Ks,t exists for 2s17. 相似文献
5.
6.
Jiangdong Ai Stefanie Gerke Gregory Gutin Yongtang Shi Zhenyu Taoqiu 《Journal of Graph Theory》2020,95(2):256-266
An orientation of is a digraph obtained from by replacing each edge by exactly one of two possible arcs with the same endpoints. We call an orientation proper if neighboring vertices have different in-degrees. The proper orientation number of a graph , denoted by , is the minimum maximum in-degree of a proper orientation of . Araujo et al asked whether there is a constant such that for every outerplanar graph and showed that for every cactus . We prove that if is a triangle-free 2-connected outerplanar graph and if is a triangle-free bridgeless outerplanar graph. 相似文献
7.
8.
《Journal of Combinatorial Theory, Series B》1987,42(3):264-273
We establish a property of minimal imperfect graphs, and use this property to generate two classes of perfect graphs. The first class contains all comparability graphs, all triangulated graphs, and two other classes of perfect graphs. The second class contains all triangulated graphs and all line-graphs of bipartite graphs. 相似文献
9.
Xingxing Yu 《Journal of Graph Theory》1991,15(1):19-27
This paper considers conditions ensuring that cycle-isomorphic graphs are isomorphic. Graphs of connectivity ? 2 that have no loops were studied in [2] and [4]. Here we characterize all graphs G of connectivity 1 such that every graph that is cycle-isomorphic to G is also isomorphic to G. 相似文献
10.
D. Artigas S. Dantas M.C. Dourado J.L. Szwarcfiter S. Yamaguchi 《Discrete Applied Mathematics》2013,161(10-11):1356-1362
11.
12.
Liu Yanpei 《数学学报(英文版)》1992,8(4):413-423
This paper provides two kinds of forbidden configurations for the rectilinear O-embeddability of triangle free planar graphs.
Meanwhile, the characterizations of the O-embeddability for outerplanar graphs and Halin graphs are found. 相似文献
13.
F.R.K. Chung 《Discrete Mathematics》1980,30(2):89-93
Let ρ(n) denote the smallest integer with the property that any graph with n vertices can be covered by ρ(n) complete bipartite subgraphs. We prove a conjecture of J.-C. Bermond by showing for any positive ?. 相似文献
14.
15.
Let G be any 3-connected graph containing n vertices and r the radius of G. Then the inequality is proved. A similar theorem concerning any (2m ?1)-connected graph G can be proved too. 相似文献
16.
For an integer , a graph is -hamiltonian if for any vertex subset with , is hamiltonian, and is -hamiltonian connected if for any vertex subset with , is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of -hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for , a line graph is -hamiltonian if and only if is -connected. In this paper we prove the following.(i) For an integer , the line graph of a claw-free graph is -hamiltonian if and only if is -connected.(ii) The line graph of a claw-free graph is 1-hamiltonian connected if and only if is 4-connected. 相似文献
17.
Van H. Vu 《Journal of Graph Theory》1996,22(2):137-149
A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic graphs of type k for every k ≥ 3. Furthermore, in the case k ≥ 5 such a family of extensions can be found at every sufficiently large order. Some bounds for the extension will also be given. © 1996 John Wiley & Sons, Inc. 相似文献
18.
19.
We introduce a simple new technique which allows us to solve several problems that can be formulated as seeking a suitable orientation of a given undirected graph. In particular, we use this technique to recognize and transitively orient comparability graphs, to recognize and represent proper circular arc graphs, and to recognize and represent proper interval graphs. As a consequence, we derive and represent proper interval graphs. As a consequence, we derive simple new proofs of a theorem of Ghouila-Houri and a theorem of Skrien. Our algorithms are conceptually simpler than (and often of comparable efficiency to) the existing algorithms for these problems. © 1995 John Wiley & Sons, Inc. 相似文献
20.
P.S. Ranjini 《Applied mathematics and computation》2011,218(3):699-702
The aim of this paper is to investigate the Zagreb indices of the line graphs of the tadpole graphs, wheel graphs and ladder graphs using the subdivision concepts. 相似文献