共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
S. Morteza Mirafzal 《Discrete Mathematics》2018,341(1):217-220
The Kneser graph has as vertices all -element subsets of and an edge between any two vertices that are disjoint. If , then is called an odd graph. Let and . In the present paper, we show that if the Kneser graph is of even order where is an odd integer or both of the integers are even, then is a vertex-transitive non Cayley graph. Although, these are special cases of Godsil [7], unlike his proof that uses some very deep group-theoretical facts, ours uses no heavy group-theoretic facts. We obtain our results by using some rather elementary facts of number theory and group theory. We show that ‘almost all’ odd graphs are of even order, and consequently are vertex-transitive non Cayley graphs. Finally, we show that if is an even integer such that is not of the form for some , then the line graph of the odd graph is a vertex-transitive non Cayley graph. 相似文献
3.
Hiranmoy Pal 《Discrete Mathematics》2018,341(4):889-895
The transition matrix of a graph corresponding to the adjacency matrix is defined by where . The graph is said to exhibit pretty good state transfer between a pair of vertices and if there exists a sequence of real numbers such that , where is a complex number of unit modulus. We present a class of circulant graphs admitting pretty good state transfer. Also we find some circulant graphs not exhibiting pretty good state transfer. This generalizes several pre-existing results on circulant graphs admitting pretty good state transfer. 相似文献
4.
Let be a graph with vertex set . A moplex of is both a clique and a module whose neighborhood is a minimal separator in or empty. A moplex ordering of is an ordered partition of for some integer into moplexes which are defined in the successive transitory elimination graphs, i.e., for , is a moplex of the graph induced by and induces a clique. In this paper we prove the terminal vertex by an execution of the lexicographical depth-first search (LexDFS for short) algorithm on belongs to a moplex whose vertices are numbered consecutively and further that the LexDFS algorithm on defines a moplex ordering of , which is similar to the result about the maximum cardinality search (MCS for short) algorithm on chordal graphs [J.R.S. Blair, B.W. Peyton, An introduction to chordal graphs and clique trees, IMA Volumes in Mathematics and its Applications, 56 (1993) pp. 1–30] and the result about the lexicographical breadth-first search (LexBFS for short) algorithm on general graphs [A. Berry, J.-P. Bordat, Separability generalizes Dirac’s theorem, Discrete Appl. Math., 84 (1998) 43–53]. As a corollary, we can obtain a simple algorithm on a chordal graph to generate all minimal separators and all maximal cliques. 相似文献
5.
The power graph of a group is a graph with vertex set and two distinct vertices are adjacent if and only if one is an integral power of the other. In this paper we find both upper and lower bounds for the spectral radius of power graph of cyclic group and characterize the graphs for which these bounds are extremal. Further we compute spectra of power graphs of dihedral group and dicyclic group partially and give bounds for the spectral radii of these graphs. 相似文献
6.
We study strong graph bundles : a concept imported from topology which generalizes both covering graphs and product graphs. Roughly speaking, a strong graph bundle always involves three graphs , and and a projection with fiber (i.e. for all ) such that the preimage of any edge of is trivial (i.e. ). Here we develop a framework to study which subgraphs of have trivial preimages (i.e. ) and this allows us to compare and classify several variations of the concept of strong graph bundle. As an application, we show that the clique operator preserves triangular graph bundles (strong graph bundles where preimages of triangles are trivial) thus yielding a new technique for the study of clique divergence of graphs. 相似文献
7.
The rainbow number for the graph in is defined to be the minimum integer such that any -edge-coloring of contains a rainbow . As one of the most important structures in graphs, the rainbow number of matchings has drawn much attention and has been extensively studied. Jendrol et al. initiated the rainbow number of matchings in planar graphs and they obtained bounds for the rainbow number of the matching in the plane triangulations, where the gap between the lower and upper bounds is . In this paper, we show that the rainbow number of the matching in maximal outerplanar graphs of order is . Using this technique, we show that the rainbow number of the matching in some subfamilies of plane triangulations of order is . The gaps between our lower and upper bounds are only . 相似文献
8.
Irving Dai 《Discrete Mathematics》2018,341(7):1932-1944
The Johnson graphs are a well-known family of combinatorial graphs whose applications and generalizations have been studied extensively in the literature. In this paper, we present a new variant of the family of Johnson graphs, the Full-Flag Johnson graphs, and discuss their combinatorial properties. We show that the Full-Flag Johnson graphs are Cayley graphs on generated by certain well-known classes of permutations and that they are in fact generalizations of permutahedra. We prove a tight bound for the diameter of the Full-Flag Johnson graph FJ and establish recursive relations between FJ and the lower-order Full-Flag Johnson graphs FJ and FJ. We apply this recursive structure to partially compute the spectrum of permutahedra. 相似文献
9.
The boxicity of a graph is the smallest integer such that is the intersection of interval graphs, or equivalently, that is the intersection graph of axis-aligned boxes in . These intersection representations can be interpreted as covering representations of the complement of with co-interval graphs, that is, complements of interval graphs. We follow the recent framework of global, local and folded covering numbers (Knauer and Ueckerdt, 2016) to define two new parameters: the local boxicity and the union boxicity of . The union boxicity of is the smallest such that can be covered with
vertex–disjoint unions of co-interval graphs, while the local boxicity of is the smallest such that can be covered with co-interval graphs, at most at every vertex.We show that for every graph we have and that each of these inequalities can be arbitrarily far apart. Moreover, we show that local and union boxicity are also characterized by intersection representations of appropriate axis-aligned boxes in . We demonstrate with a few striking examples, that in a sense, the local boxicity is a better indication for the complexity of a graph, than the classical boxicity. 相似文献
10.
In this paper, some types of vague graphs are introdaced such as -regular, -regular, -highly irregular and -highly totally irregular vague graphs are introduced and some properties of them are discussed. Comparative study between -regular (-highly irregular) vague graph and -regular (-highly totally irregular) vague graph are done. In addition, -regularity and -highly irregularity on some vague graphs, which underlying crisp graphs are a cycle or a path is also studied. Finally, some applications of regular vague graphs are given for demonstration of fullerene molecules, road transport network and wireless multihop networks. 相似文献
11.
Kiyoshi Ando 《Discrete Mathematics》2018,341(11):3003-3009
An edge of a -connected graph is said to be -contractible if the contraction of the edge results in a -connected graph. If every -connected graph with no -contractible edge has either or as a subgraph, then an unordered pair of graphs is said to be a forbidden pair for -contractible edges. We prove that is a forbidden pair for 6-contractible edges, which is an extension of a previous result due to Ando and Kawarabayashi. 相似文献
12.
It is well-known that the paths are determined by the spectrum of the adjacency matrix. For digraphs, every digraph whose underlying graph is a tree is cospectral to its underlying graph with respect to the Hermitian adjacency matrix (-cospectral). Thus every (simple) digraph whose underlying graph is isomorphic to is -cospectral to . Interestingly, there are others. This paper finds digraphs that are -cospectral with the path graph and whose underlying graphs are nonisomorphic, when is odd, and finds that such graphs do not exist when is even. In order to prove this result, all digraphs whose Hermitian spectral radius is smaller than 2 are determined. 相似文献
13.
14.
15.
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. 相似文献
16.
The independence polynomial of a graph is the generating function of the numbers of independent sets of each size. A graph of order is very well-covered if every maximal independent set has size . Levit and Mandrescu conjectured that the independence polynomial of every very well-covered graph is unimodal (that is, the sequence of coefficients is nondecreasing, then nonincreasing). In this article we show that every graph is embeddable as an induced subgraph of a very well-covered graph whose independence polynomial is unimodal, by considering the location of the roots of such polynomials. 相似文献
17.
Boris Brimkov Jennifer Edmond Robert Lazar Bernard Lidický Kacy Messerschmidt Shanise Walker 《Discrete Mathematics》2017,340(10):2538-2549
An injective coloring of a graph is an assignment of colors to the vertices of so that any two vertices with a common neighbor have distinct colors. A graph is injectively -choosable if for any list assignment , where for all , has an injective -coloring. Injective colorings have applications in the theory of error-correcting codes and are closely related to other notions of colorability. In this paper, we show that subcubic planar graphs with girth at least 6 are injectively 5-choosable. This strengthens the result of Lu?ar, ?krekovski, and Tancer that subcubic planar graphs with girth at least 7 are injectively 5-colorable. Our result also improves several other results in particular cases. 相似文献
18.
The tree-depth of is the smallest value of for which a labeling of the vertices of with elements from exists such that any path joining two vertices with the same label contains a vertex having a higher label. The graph is -critical if it has tree-depth and every proper minor of has smaller tree-depth.Motivated by a conjecture on the maximum degree of -critical graphs, we consider the property of 1-uniqueness, wherein any vertex of a critical graph can be the unique vertex receiving label 1 in an optimal labeling. Contrary to an earlier conjecture, we construct examples of critical graphs that are not 1-unique and show that 1-unique graphs can have arbitrarily many more edges than certain critical spanning subgraphs. We also show that -critical graphs on vertices are 1-unique and use 1-uniqueness to show that the Andrásfai graphs are critical with respect to tree-depth. 相似文献
19.
20.
The power graph of a finite group is the graph whose vertex set is , two distinct elements being adjacent if one is a power of the other. In this paper, we give sharp lower and upper bounds for the independence number of and characterize the groups achieving the bounds. Moreover, we determine the independence number of if is cyclic, dihedral or generalized quaternion. Finally, we classify all finite groups whose power graphs have independence number 3 or , where is the order of . 相似文献