共查询到20条相似文献,搜索用时 15 毫秒
1.
On optimizing edge connectivity of product graphs 总被引:1,自引:0,他引:1
Jianping Ou 《Discrete Mathematics》2011,(6):172
This work studies the super edge connectivity and super restricted edge connectivity of direct product graphs, Cartesian product graphs, strong product graphs and lexicographic product graphs. As a result, sufficient conditions for optimizing the edge connectivity and restricted edge connectivity of these graphs are presented. 相似文献
2.
Štefko Miklavi? Martin Milani? 《Discrete Applied Mathematics》2011,159(11):1148-1159
In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al. 相似文献
3.
充分利用图的字典积的结构证明了以下结论:如果图G_1的每连通分支都非平凡,图G_2的阶数大于3,那么它们的字典积G_1[G_2]具有非零3-流. 相似文献
4.
文章给出了两个图的笛卡儿积及字典式的积为最大边连通的、最大连通的、super-λ,super-κ及hyper-κ的充分条件,同时证明了其中一些条件也是必要的.此外,对这两种积的局部割集和广义割集的性质也进行了考虑. 相似文献
5.
图的字典序积和自同态幺半群 总被引:4,自引:1,他引:3
F.Harary ̄[1]和G.Sabidussi ̄[2]考虑过图X和y的字典序积X[Y]的自同构群AutX[Y]与它们各自的自同构群的圈积AutX[AutY]的关系,并给出了两者相等的一种刻划.在本文,我们考虑更广意义上的问题,即X[Y]的自同态幺半群EndX[Y]与各自的自同态幺半群的圈积EndX[EndY]的关系,也给出了两者相等的一种刻划,同时得到了下面结果:如果X和Y都是不含K_3导出子图的连通图,且其中之一图有奇数围长,那么EndX[Y]=EndX[EndY]. 相似文献
6.
7.
Many large graphs can be constructed from existing smaller graphs by using graph operations, for example, the Cartesian product and the lexicographic product. Many properties of such large graphs are closely related to those of the corresponding smaller ones. In this short note, we give some properties of the lexicographic products of vertex-transitive and of edge-transitive graphs. In particular, we show that the lexicographic product of Cayley graphs is a Cayley graph. 相似文献
8.
Roland Kaschek 《Discrete Mathematics》2010,310(8):1275-1281
This paper proves a necessary and sufficient condition for the endomorphism monoid of a lexicographic product G[H] of graphs G,H to be the wreath product of the monoids and . The paper also gives respective necessary and sufficient conditions for specialized cases such as for unretractive or triangle-free graphs G. 相似文献
9.
Hailong Hou 《Discrete Mathematics》2008,308(17):3888-3896
In this paper, we give several approaches to construct new End-regular (-orthodox) graphs by means of the join and the lexicographic product of two graphs with certain conditions. In particular, the join of two connected bipartite graphs with a regular (orthodox) endomorphism monoid is explicitly described. 相似文献
10.
Some graphs admit drawings in the Euclidean plane (k-space) in such a (natural) way, that edges are represented as line segments of unit length. We say that they have the unit distance property.The influence of graph operations on the unit distance property is discussed. It is proved that the Cartesian product preserves the unit distance property in the Euclidean plane, while graph union, join, tensor product, strong product, lexicographic product and corona do not. It is proved that the Cartesian product preserves the unit distance property also in higher dimensions. 相似文献
11.
Jan Jakubik 《Czechoslovak Mathematical Journal》2001,51(1):127-138
The notion of the half linearly ordered group (and, more generally, of the half lattice ordered group) was introduced by Giraudet and Lucas [2]. In the present paper we define the lexicographic product of half linearly ordered groups. This definition includes as a particular case the lexicographic product of linearly ordered groups. We investigate the problem of the existence of isomorphic refinements of two lexicographic product decompositions of a half linearly ordered group. The analogous problem for linearly ordered groups was dealt with by Maltsev [5]; his result was generalized by Fuchs [1] and the author [3]. The isomorphic refinements of small direct product decompositions of half lattice ordered groups were studied in [4]. 相似文献
12.
《Discrete Mathematics》2023,346(1):113162
The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths. 相似文献
13.
The values of the chromatic and achromatic number, point- and line-connectivity, and point independence number of the lexicographic product of two graphs are examined in relation to the values of the respective parameters on the factor graphs. 相似文献
14.
We prove that if G and H are graphs containing at least one edge each, then their lexicographic product G[H] is weakly pancyclic, i. e., it contains a cycle of every length between the length of a shortest cycle and that of a longest one. This supports
some conjectures on locally connected graphs and on product graphs. We obtain an analogous result on even cycles in products
G[H] that are bipartite. We also investigate toughness conditions on G implying that G[H] is hamiltonian (and hence pancyclic).
Supported by the project LN00A056 of the Czech Ministry of Education 相似文献
15.
Milan Demko 《Czechoslovak Mathematical Journal》2007,57(2):607-629
In this paper we prove for an hl-loop Q an assertion analogous to the result of Jakubík concerning lexicographic products of half linearly ordered groups. We found
conditions under which any two lexicographic product decompositions of an hl-loop Q with a finite number of lexicographic factors have isomorphic refinements. 相似文献
16.
《Quaestiones Mathematicae》2013,36(2):217-232
AbstractIn this paper, general results on the toughness of a graph are considered. Firstly the link between toughness and connectivity is explored and then results linking toughness and the parameters binding number and integrity are given. Further, the toughness of product graphs is discussed including general results for the lexicographic product. The paper concludes with some observations on toughness and hamiltoni-city. 相似文献
17.
字典乘积有向图G_1→⊙G_2是通过已知阶数较小的有向图G_1和G_2构造来的,这些小有向图G_1和G_2的拓扑结构和性质肯定影响大有向图G_1→⊙G_2的拓扑结构和性质.运用群论方法,证明了有向图字典乘积的一些代数性质,如:结合律、分配律等. 相似文献
18.
Ulrich Knauer 《Journal of Graph Theory》1987,11(3):429-440
Graphs without proper endomorphisms are the subject of this article. It is shown that the join of two graphs has this property if and only if both summands have it, and that the lexicographic product of a complete graph or an odd circuit as first factors has this property if and only if the second factor has it. A somewhat stronger theorem is proved if the lexicographic product has no proper strong endomorphism. The corresponding result for the join is the same as for usual endomorphisms. 相似文献
19.
Nair Abreu Domingos M. Cardoso Paula Carvalho Cybele T.M. Vinagre 《Discrete Mathematics》2017,340(1):3235-3244
Consider two graphs and . Let be the lexicographic product of and , where is the lexicographic product of the graph by itself times. In this paper, we determine the spectrum of and when and are regular and the Laplacian spectrum of and for and arbitrary. Particular emphasis is given to the least eigenvalue of the adjacency matrix in the case of lexicographic powers of regular graphs, and to the algebraic connectivity and the largest Laplacian eigenvalues in the case of lexicographic powers of arbitrary graphs. This approach allows the determination of the spectrum (in case of regular graphs) and Laplacian spectrum (for arbitrary graphs) of huge graphs. As an example, the spectrum of the lexicographic power of the Petersen graph with the googol number (that is, 10100 ) of vertices is determined. The paper finishes with the extension of some well known spectral and combinatorial invariant properties of graphs to its lexicographic powers. 相似文献
20.
An anti-magic labeling of a finite simple undirected graph with p vertices and q edges is a bijection from the set of edges to the set of integers {1,2,…,q} such that the vertex sums are pairwise distinct, where the vertex sum at one vertex is the sum of labels of all edges incident to such vertex. A graph is called anti-magic if it admits an anti-magic labeling. Hartsfield and Ringel conjectured in 1990 that all connected graphs except K2 are anti-magic. Recently, Alon et al. showed that this conjecture is true for dense graphs, i.e. it is true for p-vertex graphs with minimum degree Ω(logp). In this article, new classes of sparse anti-magic graphs are constructed through Cartesian products and lexicographic products. 相似文献