共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
A set of vertices of a graph is locating if every two distinct vertices outside have distinct neighbors in ; that is, for distinct vertices and outside , , where denotes the open neighborhood of . If is also a dominating set (total dominating set), it is called a locating-dominating set (respectively, locating-total dominating set) of . A graph is twin-free if every two distinct vertices of have distinct open and closed neighborhoods. It is conjectured (Garijo et al., 2014 [15]) and (Foucaud and Henning, 2016 [12]) respectively, that any twin-free graph without isolated vertices has a locating-dominating set of size at most one-half its order and a locating-total dominating set of size at most two-thirds its order. In this paper, we prove these two conjectures for the class of line graphs. Both bounds are tight for this class, in the sense that there are infinitely many connected line graphs for which equality holds in the bounds. 相似文献
3.
4.
《Discrete Mathematics》2007,307(11-12):1291-1297
5.
6.
Let be a finite group, written multiplicatively. The Davenport constant of is the smallest positive integer such that every sequence of with elements has a non-empty subsequence with product . Let be the Dihedral Group of order and be the Dicyclic Group of order . Zhuang and Gao (2005) showed that and Bass (2007) showed that . In this paper, we give explicit characterizations of all sequences of such that and is free of subsequences whose product is 1, where is equal to or for some . 相似文献
7.
8.
Katarzyna Jesse-Józefczyk 《Discrete Mathematics》2012,312(23):3451-3456
9.
Xiaoyan Chen 《Statistics & probability letters》2010,80(5-6):519-526
10.
11.
Two graphs are said to be -cospectral (respectively, -cospectral) if they have the same (respectively, signless) Laplacian spectra, and a graph is said to be (respectively, ) if there does not exist other non-isomorphic graph such that and are -cospectral (respectively, -cospectral). Let be the degree sequence of a graph with vertices. In this paper, we prove that except for two exceptions (respectively, the graphs with ), if is -cospectral (respectively, -cospectral) with a connected graph and , then has the same degree sequence as . A spider graph is a unicyclic graph obtained by attaching some paths to a common vertex of the cycle. As an application of our result, we show that every spider graph and its complement graph are both , which extends the corresponding results of Haemers et al. (2008), Liu et al. (2011), Zhang et al. (2009) and Yu et al. (2014). 相似文献
12.
Let and be the adjacency matrix and the degree matrix of a graph , respectively. The matrix is called the signless Laplacian matrix of . The spectrum of the matrix is called the Q-spectrum of . A graph is said to be determined by its Q-spectrum if there is no other non-isomorphic graph with the same Q-spectrum. In this paper, we prove that all starlike trees whose maximum degree exceed are determined by their Q-spectra. 相似文献
13.
14.
A kernel by properly colored paths of an arc-colored digraph is a set of vertices of such that (i) no two vertices of are connected by a properly colored directed path in , and (ii) every vertex outside can reach by a properly colored directed path in . In this paper, we conjecture that every arc-colored digraph with all cycles properly colored has such a kernel and verify the conjecture for digraphs with no intersecting cycles, semi-complete digraphs and bipartite tournaments, respectively. Moreover, weaker conditions for the latter two classes of digraphs are given. 相似文献
15.
A set of vertices in a graph is an independent dominating set of if is an independent set and every vertex not in is adjacent to a vertex in . The independent domination number, , of is the minimum cardinality of an independent dominating set. In this paper, we extend the work of Henning, Löwenstein, and Rautenbach (2014) who proved that if is a bipartite, cubic graph of order and of girth at least , then . We show that the bipartite condition can be relaxed, and prove that if is a cubic graph of order and of girth at least , then . 相似文献
16.
Given a graph , a set is a dominating set of if every vertex of is either in or adjacent to a vertex in . The domination number of , denoted , is the minimum cardinality of a dominating set of . Vizing’s conjecture states that for any graphs and where denotes the Cartesian product of and . In this paper, we continue the work by Anderson et al. (2016) by studying the domination number of the hierarchical product. Specifically, we show that partitioning the vertex set of a graph in a particular way shows a trend in the lower bound of the domination number of the product, providing further evidence that the conjecture is true. 相似文献
17.
18.
19.
20.
Peter Dankelmann 《Discrete Mathematics》2010,310(17-18):2334-2344