共查询到20条相似文献,搜索用时 703 毫秒
1.
A. A. Dobrynin 《Journal of Applied and Industrial Mathematics》2018,12(4):642-647
The transmission of a vertex v in a graph is the sum of the distances from v to all other vertices of the graph. In a transmission irregular graph, the transmissions of all vertices are pairwise distinct. It is known that almost all graphs are not transmission irregular. Some infinite family of transmission irregular trees was constructed by Alizadeh and Klav?ar [Appl.Math. Comput. 328, 113–118 (2018)] and the following problemwas formulated: Is there an infinite family of 2-connected graphs with the property? In this article, we construct an infinite family of 2-connected transmission irregular graphs. 相似文献
2.
3.
4.
《Discrete Mathematics》2019,342(4):1195-1212
A graph is -saturated for a graph , if does not contain a copy of but adding any new edge to results in such a copy. An -saturated graph on a given number of vertices always exists and the properties of such graphs, for example their highest density, have been studied intensively.A graph is -induced-saturated if does not have an induced subgraph isomorphic to , but adding an edge to from its complement or deleting an edge from results in an induced copy of . It is not immediate anymore that -induced-saturated graphs exist. In fact, Martin and Smith (2012) showed that there is no -induced-saturated graph. Behrens et al. (2016) proved that if belongs to a few simple classes of graphs such as a class of odd cycles of length at least 5, stars of size at least 2, or matchings of size at least 2, then there is an -induced-saturated graph.This paper addresses the existence question for -induced-saturated graphs. It is shown that Cartesian products of cliques are -induced-saturated graphs for in several infinite families, including large families of trees. A complete characterization of all connected graphs for which a Cartesian product of two cliques is an -induced-saturated graph is given. Finally, several results on induced saturation for prime graphs and families of graphs are provided. 相似文献
5.
In the b-coloring problem, we aim to assign colors from a set to the vertices of a graph in such a way that adjacent vertices do not receive the same color, and for every we have a -colored vertex in such that every color in is assigned to at least one of ’s neighbors. It has been shown that b-coloring is NP-complete, so we propose in this article an approach for the problem under integer programming techniques. To this end, we give an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and analyze facetness conditions for them. Finally, we show computational evidence suggesting that the given inequalities may be useful in a branch-and-cut environment. 相似文献
6.
Jie Hu Guanghui Wang Jianliang Wu Donglei Yang Xiaowei Yu 《Discrete Mathematics》2019,342(5):1392-1402
Let be a positive integer. An adjacent vertex distinguishing (for short, AVD) total--coloring of a graph is a proper total--coloring of such that any two adjacent vertices have different color sets, where the color set of a vertex contains the color of and the colors of its incident edges. It was conjectured that any graph with maximum degree has an AVD total-()-coloring. The conjecture was confirmed for any graph with maximum degree at most 4 and any planar graph with maximum degree at least 10. In this paper, we verify the conjecture for all planar graphs with maximum degree at least 9. Moreover, we prove that any planar graph with maximum degree at least 10 has an AVD total-()-coloring and the bound is sharp. 相似文献
7.
Let G be a finite, connected graph. The average distance of a vertex v of G is the arithmetic mean of the distances from v to all other vertices of G. The remoteness and the proximity of G are the maximum and the minimum of the average distances of the vertices of G. In this paper, we present a sharp upper bound on the remoteness of a triangle-free graph of given order and minimum degree, and a corresponding bound on the proximity, which is sharp apart from an additive constant. We also present upper bounds on the remoteness and proximity of -free graphs of given order and minimum degree, and we demonstrate that these are close to being best possible. 相似文献
8.
《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. 相似文献
9.
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. 相似文献
10.
Ademir Hujdurović 《Discrete Mathematics》2019,342(9):2542-2548
A canonical double cover of a graph is the direct product of and the complete graph on two vertices. In order to answer the question when a canonical double cover of a given graph is a Cayley graph, in 1992 Maru?i? et al. introduced the concept of generalized Cayley graphs. In this paper this concept is generalized to a wider class of graphs, the so-called extended generalized Cayley graphs. It is proved that the canonical double cover of a connected non-bipartite graph is a Cayley graph if and only if is an extended generalized Cayley graph. This corrects an incorrectly stated claim in [Discrete Math. 102 (1992), 279–285]. 相似文献
11.
An incidence of a graph is a pair where is a vertex of and is an edge of incident to . Two incidences and of are adjacent whenever (i) , or (ii) , or (iii) or . An incidence-coloring of is a mapping from the set of incidences of to a set of colors such that every two adjacent incidences receive distinct colors. The notion of incidence coloring has been introduced by Brualdi and Quinn Massey (1993) from a relation to strong edge coloring, and since then, has attracted a lot of attention by many authors.On a list version of incidence coloring, it was shown by Benmedjdoub et al. (2017) that every Hamiltonian cubic graph is incidence 6-choosable. In this paper, we show that every cubic (loopless) multigraph is incidence 6-choosable. As a direct consequence, it implies that the list strong chromatic index of a -bipartite graph is at most 6, where a (2,3)-bipartite graph is a bipartite graph such that one partite set has maximum degree at most 2 and the other partite set has maximum degree at most 3. 相似文献
12.
13.
14.
Hemanshu Kaul Jeffrey A. Mudrock Michael J. Pelsmajer Benjamin Reiniger 《Discrete Mathematics》2019,342(8):2371-2383
In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. A -assignment for a graph specifies a list of available colors for each vertex of . An -coloring assigns a color to each vertex from its list . For each color , let be the number of vertices whose list contains . A proportional-coloring of is a proper -coloring in which each color is used or times. A graph is proportionally-choosable if a proportional -coloring of exists whenever is a -assignment for . We show that if a graph is proportionally -choosable, then every subgraph of is also proportionally -choosable and also is proportionally -choosable, unlike equitable choosability for which analogous claims would be false. We also show that any graph is proportionally -choosable whenever , and we use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques. 相似文献
15.
16.
Aleksander Vesel 《Discrete Mathematics》2019,342(4):1139-1146
The generalized Fibonacci cube is the graph obtained from the -cube by removing all vertices that contain a given binary string as a substring. If is an induced subgraph of , then the cube-complement of is the graph induced by the vertices of which are not in . In particular, the cube-complement of a generalized Fibonacci cube is the subgraph of induced by the set of all vertices that contain as a substring. The questions whether a cube-complement of a generalized Fibonacci cube is (i) connected, (ii) an isometric subgraph of a hypercube or (iii) a median graph are studied. Questions (ii) and (iii) are completely solved, i.e. the sets of binary strings that allow a graph of this class to be an isometric subgraph of a hypercube or a median graph are given. The cube-complement of a daisy cube is also studied. 相似文献
17.
《Discrete Mathematics》2020,343(1):111641
A graph is called -induced-saturated if does not contain an induced copy of , but removing any edge from creates an induced copy of and adding any edge of to creates an induced copy of . Martin and Smith studied a related problem, and proved that there does not exist a -induced-saturated graph, where is the path on 4 vertices. Axenovich and Csikós gave examples of families of graphs for which -induced-saturated graph exists, and asked if there exists a -induced-saturated graph when . Our aim in this short note is to show that there exists a -induced-saturated graph. 相似文献
19.
20.
William M. Kantor 《Discrete Mathematics》2019,342(10):2886-2892
If is a finite group and or for a prime power then, for infinitely many integers , there is a 2--design for which . 相似文献