共查询到20条相似文献,搜索用时 15 毫秒
1.
Recently Alon and Friedland have shown that graphs which are the union of complete regular bipartite graphs have the maximum number of 1-factors over all graphs with the same degree sequence. We identify two families of graphs that have the maximum number of 1-factors over all graphs with the same number of vertices and edges: the almost regular graphs which are unions of complete regular bipartite graphs, and complete graphs with a matching removed. The first family is determined using the Alon and Friedland bound. For the second family, we show that a graph transformation which is known to increase network reliability also increases the number of 1-factors. In fact, more is true: this graph transformation increases the number of k-factors for all k≥1, and “in reverse” also shows that in general, threshold graphs have the fewest k-factors. We are then able to determine precisely which threshold graphs have the fewest 1-factors. We conjecture that the same graphs have the fewest k-factors for all k≥2 as well. 相似文献
2.
G是顶点集为{v_1,v_2,…,v_n}的连通简单图,G_1,G_2,…,G_n是有限图。联并图G[G_1,G_2,…,G_n】是按如下方式在G_1UG_2U…UG_n上加边而成的图:在G_i和G_j之间的任何两个顶点间加边,若v_i和v_j在G中相邻.[7]给出了两个距离正则图的卡氏积的距离谱.本文计算了联并图和距离正则图的卡氏积及两个联并图的卡氏积的距离谱.在此基础之上,我们得到了两个利用联并图与非同谱距离正则等能量图作卡氏积及联并图作卡氏积构造非同谱等距离能量图族的方法. 相似文献
3.
Order - Cover-incomparability graphs (C-I graphs) are graphs whose edge-set is the union of edge-sets of the incomparability graph and the cover graph of some poset. C-I graphs captured attention... 相似文献
4.
Cover-Incomparability Graphs of Posets 总被引:1,自引:1,他引:0
Boštjan Brešar Manoj Changat Sandi Klavžar Matjaž Kovše Joseph Mathews Antony Mathews 《Order》2008,25(4):335-347
Cover-incomparability graphs (C-I graphs, for short) are introduced, whose edge-set is the union of edge-sets of the incomparability
and the cover graph of a poset. Posets whose C-I graphs are chordal (resp. distance-hereditary, Ptolemaic) are characterized
in terms of forbidden isometric subposets, and a general approach for studying C-I graphs is proposed. Several open problems
are also stated. 相似文献
5.
Halina Bielak 《Discrete Mathematics》2010,310(9):1501-1505
We give the Ramsey number for a disjoint union of some G-good graphs versus a graph G generalizing the results of Stahl (1975) [5] and Baskoro et al. (2006) [1] and the previous result of the author Bielak (2009) [2]. Moreover, a family of G-good graphs with s(G)>1 is presented. 相似文献
6.
Martin Kochol 《Graphs and Combinatorics》1992,8(4):313-315
The well known theorem of Nash-Williams determines the graphs that are union ofk edge disjoint forests. The main result presented in this note is that any graph which is the union ofk edge disjoint forests is in fact a union ofk such forests in which if a vertex has degree at least 3 in one of the forests then its degree is positive in all the other
forests. We also discuss consequences of this result with respect to the arboricity of regular graphs. 相似文献
7.
目的是研究局部传递图的性质和分类.运用置换群和陪集图的理论,获得了关于素数立方阶群局部传递图的完全分类,证明了这些图是一些互不相交的关于素数立方阶群边传递图的并. 相似文献
8.
Jay R Goldman J.T Joichi Dennis E White 《Journal of Combinatorial Theory, Series B》1978,25(2):135-142
This paper studies the relationship between the rook vector of a general board and the chromatic structure of an associated set of graphs. We prove that every rook vector is a chromatic vector. We give algebraic relations between the factorial polynomials of two boards and their union and sum, and the chromatic polynomials of two graphs and their union and sum. 相似文献
9.
Embeddings of graphs into ℝ3 such that each line contains minimal possible number of points of the image are considered. It is proved that for every embedding
into ℝ3 of a graph containing the disjoint union of two Kuratowski-Pontryagin graphs there exists a line containing four points of
the image or more. Therefore, disjoint unions of Kuratowski-Pontryagin graphs are minimal 3-nonembeddable graphs. 相似文献
10.
Edward R. Scheinerman 《Journal of Graph Theory》1986,10(4):545-551
A class of graphs is hereditary if it is closed under taking induced subgraphs. Classes associated with graph representations have “composition sequences” and we show that this concept is equivalent to a notion of “amalgamation” which generalizes disjoint union of graphs. We also discuss how general hereditary classes of graphs are built up from representation classes. 相似文献
11.
We consider strongly regular graphs defined on a finite field by taking the union of some cyclotomic classes as difference set. Several new examples are found. 相似文献
12.
Angsuman Das 《Linear and Multilinear Algebra》2017,65(6):1276-1287
In this paper, we introduce a graph structure, called non-zero component union graph on finite-dimensional vector spaces. We show that the graph is connected and find its domination number, clique number and chromatic number. It is shown that two non-zero component union graphs are isomorphic if and only if the base vector spaces are isomorphic. In case of finite fields, we study the edge-connectivity and condition under which the graph is Eulerian. Moreover, we provide a lower bound for the independence number of the graph. Finally, we come up with a structural characterization of non-zero component union graph. 相似文献
13.
Oliver Schaudt 《Discrete Mathematics》2011,311(18-19):2095-2101
Recently, Bacsó and Tuza gave a full characterization of the graphs for which every connected induced subgraph has a connected dominating subgraph satisfying an arbitrary prescribed hereditary property. Using their result, we derive a similar characterization of the graphs for which any isolate-free induced subgraph has a total dominating subgraph that satisfies a prescribed additive hereditary property. In particular, we give a characterization for the case where the total dominating subgraphs are a disjoint union of complete graphs. This yields a characterization of the graphs for which every isolate-free induced subgraph has a vertex-dominating induced matching, a so-called induced paired-dominating set. 相似文献
14.
Haicheng Ma 《Discrete Mathematics》2010,310(24):3648-3652
A graph is said to be determined by its adjacency spectrum (DS for short) if there is no other non-isomorphic graph with the same spectrum. In this paper, we focus our attention on the spectral characterization of the union of complete multipartite graph and some isolated vertices, and all its cospectral graphs are obtained. By the results, some complete multipartite graphs determined by their adjacency spectrum are also given. This extends several previous results of spectral characterization related to the complete multipartite graphs. 相似文献
15.
Cographs form the minimal family of graphs containing K1 that is closed with respect to complementation and disjoint union. We discuss vertex partitions of graphs into the smallest number of cographs. We introduce a new parameter, calling the minimum order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show that both bounds are sharp for graphs with arbitrarily high girth. This provides an alternative proof to a result by Broere and Mynhardt; namely, there exist triangle-free graphs with arbitrarily large c-chromatic numbers. We show that any planar graph with girth at least 11 has a c-chromatic number at most two. We close with several remarks on computational complexity. In particular, we show that computing the c-chromatic number is NP-complete for planar graphs. 相似文献
16.
The main result is that if m and k are odd integers with m ≥ k ≥ 1, then any graph which is the union of m graphs of maximum valence k is also the union of k graphs of maximum valence m. This is not generally true if k > m. 相似文献
17.
Elaine M. Eschen Chính T. Hong Mark D. T. Petrick R. Sritharan 《Journal of Graph Theory》2005,48(4):277-298
A biclique cutset is a cutset that induces the disjoint union of two cliques. A hole is an induced cycle with at least five vertices. A graph is biclique separable if it has no holes and each induced subgraph that is not a clique contains a clique cutset or a biclique cutset. The class of biclique separable graphs contains several well‐studied graph classes, including triangulated graphs. We prove that for the class of biclique separable graphs, the recognition problem, the vertex coloring problem, and the clique problem can be solved efficiently. Our algorithms also yield a proof that biclique separable graphs are perfect. Our coloring algorithm is actually more general and can be applied to graphs that can be decomposed via a special type of biclique cutset. Our algorithms are based on structural results on biclique separable graphs developed in this paper. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 277–298, 2005 相似文献
18.
《Discrete Mathematics》2019,342(4):1213-1222
Two new techniques are introduced into the theory of the domination game. The cutting lemma bounds the game domination number of a partially dominated graph with the game domination number of a suitably modified partially dominated graph. The union lemma bounds the S-game domination number of a disjoint union of paths using appropriate weighting functions. Using these tools a conjecture asserting that the so-called three legged spiders are game domination critical graphs is proved. An extended cutting lemma is also derived and all game domination critical trees on 18, 19, and 20 vertices are listed. 相似文献
19.
《佛山科学技术学院》2014,6(4):505-522
In this paper, we discuss some properties of the self complement and self weak complement bipolar fuzzy graphs, and get a sufficient condition for a bipolar fuzzy graph to be the self weak complement bipolar fuzzy graph. Also we investigate relations between operations union, join, and complement on bipolar fuzzy graphs. 相似文献
20.
拟序是图能量排序中一种有效方法,基于该方法,已经得到了大量图类的极值能量排序的结果.Gutman给出了点数和为n的两条路的并的能量排序,而三条路的并的能量排序没有一个理想的结论.本文利用拟序法给出点数和为n的三条路的并的极值能量及一类图能量的排序. 相似文献