共查询到20条相似文献,搜索用时 421 毫秒
1.
《Discrete Mathematics》2022,345(3):112706
The power of a graph , , is the graph whose vertex set is V and in which two distinct vertices are adjacent if and only if their distance in G is at most k. This article proves various eigenvalue bounds for the independence number and chromatic number of which purely depend on the spectrum of G, together with a method to optimize them. Our bounds for the k-independence number also work for its quantum counterpart, which is not known to be a computable parameter in general, thus justifying the use of integer programming to optimize them. Some of the bounds previously known in the literature follow as a corollary of our main results. Infinite families of graphs where the bounds are sharp are presented as well. 相似文献
2.
Kiyoshi Ando 《Discrete Mathematics》2019,342(12):111598
An edge of a -connected graph is said to be -contractible if the contraction of the edge results in a -connected graph. For a graph and a vertex of , let be the subgraph induced by the neighborhood of . We prove that if has less than edges for any vertex of a -connected graph , then has a -contractible edge. We also show that the bound is sharp. 相似文献
3.
The disjoint shortest paths problem (-DSPP) on a graph with source–sink pairs asks if there exist pairwise edge- or vertex-disjoint shortest –-paths. It is known to be NP-complete if is part of the input. Restricting to -DSPP with strictly positive lengths, it becomes solvable in polynomial time. We extend this result by allowing zero edge lengths and give a polynomial-time algorithm based on dynamic programming for -DSPP on undirected graphs with non-negative edge lengths. 相似文献
4.
Let be a connected graph. The eccentricity of a vertex is the distance from to a vertex farthest from . The average eccentricity of is defined as the average of the eccentricities of the vertices of , i.e., as , where is the vertex set of . For , the -packing number of is the largest cardinality of a set of vertices of whose pairwise distance is greater than . A -dominating set of is a set of vertices such that every vertex of is within distance from some vertex of . The -domination number (connected -domination number) of is the minimum cardinality of a -dominating set (of a -dominating set that induces a connected subgraph) of . For , the -packing number, the -domination number and the connected -domination number are the independence number, the domination number and the connected domination number, respectively. In this paper we present upper bounds on the average eccentricity of graphs in terms of order and either -packing number, -domination number or connected -domination number. 相似文献
5.
《Discrete Mathematics》2019,342(4):927-933
Given a fixed positive integer , the -planar local crossing number of a graph , denoted by , is the minimum positive integer such that can be decomposed into subgraphs, each of which can be drawn in a plane such that no edge is crossed more than times. In this note, we show that under certain natural restrictions, the ratio is of order , which is analogous to the result of Pach et al. (2018) for the -planar crossing number (defined as the minimum positive integer for which there is a -planar drawing of with total edge crossings). As a corollary of our proof we show that, under similar restrictions, one may obtain a -planar drawing of with both the total number of edge crossings as well as the maximum number of times any edge is crossed essentially matching the best known bounds. Our proof relies on the crossing number inequality and several probabilistic tools such as concentration of measure and the Lovász local lemma. 相似文献
6.
A star edge coloring of a graph is a proper edge coloring such that every connected 2-colored subgraph is a path with at most 3 edges. Deng et al. and Bezegová et al. independently show that the star chromatic index of a tree with maximum degree is at most , which is tight. In this paper, we study the list star edge coloring of -degenerate graphs. Let be the list star chromatic index of : the minimum such that for every -list assignment for the edges, has a star edge coloring from . By introducing a stronger coloring, we show with a very concise proof that the upper bound on the star chromatic index of trees also holds for list star chromatic index of trees, i.e. for any tree with maximum degree . And then by applying some orientation technique we present two upper bounds for list star chromatic index of -degenerate graphs. 相似文献
7.
《Discrete Mathematics》2021,344(12):112622
A Deza graph G with parameters is a k-regular graph with n vertices such that any two distinct vertices have b or a common neighbours. The children and of a Deza graph G are defined on the vertex set of G such that every two distinct vertices are adjacent in or if and only if they have a or b common neighbours, respectively. A strongly Deza graph is a Deza graph with strongly regular children. In this paper we give a spectral characterisation of strongly Deza graphs, show relationships between eigenvalues, and study strongly Deza graphs which are distance-regular. 相似文献
8.
9.
10.
《Discrete Mathematics》2023,346(2):113254
This article gives some fundamental introduction to spectra of mixed graphs via its k-generalized Hermitian adjacency matrix. This matrix is indexed by the vertices of the mixed graph, and the entry corresponding to an arc from u to v is equal to the kth root of unity (and its symmetric entry is ); the entry corresponding to an undirected edge is equal to 1, and 0 otherwise. For all positive integers k, the non-zero entries of the above matrix are chosen from the gain set , which is not closed under multiplication when . In this paper, for all positive integers k, we extract all the mixed graphs whose k-generalized Hermitian adjacency rank (-rank for short) is 3, which partially answers a question proposed by Wissing and van Dam [34]. Furthermore, we study the spectral determination of mixed graphs with -rank 2 and 3, respectively. 相似文献
11.
Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs and , the -colored Gallai–Ramsey number is defined to be the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete graph contains a monochromatic copy of . In this paper, we first provide some exact values and bounds of . Moreover, we define the -colored bipartite Gallai–Ramsey number as the minimum integer such that and for every , every rainbow -free coloring (using all colors) of the complete bipartite graph contains a monochromatic copy of . Furthermore, we describe the structures of complete bipartite graph with no rainbow and , respectively. Finally, we find the exact values of (), (where is a subgraph of ), and by using the structural results. 相似文献
12.
Sarah Mayes-Tang 《Journal of Pure and Applied Algebra》2019,223(2):571-579
Given an ideal I we investigate the decompositions of Betti diagrams of the graded family of ideals formed by taking powers of I. We prove conjectures of Engström from [5] and show that there is a stabilization in the Boij–Söderberg decompositions of for when I is a homogeneous ideal with generators in a single degree. In particular, the number of terms in the decompositions with positive coefficients remains constant for , the pure diagrams appearing in each decomposition have the same shape, and the coefficients of these diagrams are given by polynomials in k. We also show that a similar result holds for decompositions with arbitrary coefficients arising from other chains of pure diagrams. 相似文献
13.
We present a concept called the branch-depth of a connectivity function, that generalizes the tree-depth of graphs. Then we prove two theorems showing that this concept aligns closely with the notions of tree-depth and shrub-depth of graphs as follows. For a graph and a subset of we let be the number of vertices incident with an edge in and an edge in . For a subset of , let be the rank of the adjacency matrix between and over the binary field. We prove that a class of graphs has bounded tree-depth if and only if the corresponding class of functions has bounded branch-depth and similarly a class of graphs has bounded shrub-depth if and only if the corresponding class of functions has bounded branch-depth, which we call the rank-depth of graphs.Furthermore we investigate various potential generalizations of tree-depth to matroids and prove that matroids representable over a fixed finite field having no large circuits are well-quasi-ordered by restriction. 相似文献
14.
In this paper we consider the relation between the spectrum and the number of short cycles in large graphs. Suppose is a sequence of finite and connected graphs that share a common universal cover and such that the proportion of eigenvalues of that lie within the support of the spectrum of tends to 1 in the large limit. This is a weak notion of being Ramanujan. We prove such a sequence of graphs is asymptotically locally tree-like. This is deduced by way of an analogous theorem proved for certain infinite sofic graphs and unimodular networks, which extends results for regular graphs and certain infinite Cayley graphs. 相似文献
15.
《Discrete Mathematics》2022,345(9):112942
A graph G is k-degenerate if every subgraph of G has a vertex with degree at most k. Using the Euler's formula, one can obtain that planar graphs without 3-cycles are 3-degenerate. Wang and Lih, and Fijav? et al. proved the analogue results for planar graphs without 5-cycles and planar graphs without 6-cycles, respectively. Recently, Liu et al. showed that planar graphs without 3-cycles adjacent to 5-cycles are 3-degenerate. In this work, we generalized all aforementioned results by showing that planar graphs without mutually adjacent 3-,5-, and 6-cycles are 3-degenerate. A graph G without mutually adjacent 3-,5-, and 6-cycles means that G cannot contain three graphs, say , and , where is a 3-cycle, is a 5-cycle, and is a 6-cycle such that each pair of , and are adjacent. As an immediate consequence, we have that every planar graph without mutually adjacent 3-,5-, and 6-cycles is DP-4-colorable. This consequence also generalizes the result by Chen et al that planar graphs without 5-cycles adjacent to 6-cycles are DP-4-colorable. 相似文献
16.
17.
An edge of a -connected graph is said to be -contractible if its contraction results in a -connected graph. A -connected graph without -contractible edge is said to be contraction critically -connected. Y. Egawa and W. Mader, independently, showed that the minimum degree of a contraction critical -connected graph is at most . Hence, the minimum degree of a contraction critical 8-connected graph is either 8 or 9. This paper shows that a graph is a contraction critical 8-connected graph with minimum degree 9 if and only if is the strong product of a contraction critical 4-connected graph and . 相似文献
18.
19.
20.
Define a -star to be the complete bipartite graph . In a 2014 article, Hoffman and Roberts prove that a partial -star decomposition of can be embedded in a -star decomposition of where is at most if is odd and if is even. In our work, we offer a straightforward construction for embedding partial -star designs and lower these bounds to and , respectively. 相似文献