共查询到20条相似文献,搜索用时 31 毫秒
1.
2.
3.
4.
A Roman domination function on a graph G=(V(G),E(G)) is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of a Roman dominating function is the value f(V(G))=∑u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. Cockayne et al. [E. J. Cockayne et al. Roman domination in graphs, Discrete Mathematics 278 (2004) 11-22] showed that γ(G)≤γR(G)≤2γ(G) and defined a graph G to be Roman if γR(G)=2γ(G). In this article, the authors gave several classes of Roman graphs: P3k,P3k+2,C3k,C3k+2 for k≥1, Km,n for min{m,n}≠2, and any graph G with γ(G)=1; In this paper, we research on regular Roman graphs and prove that: (1) the circulant graphs and , n⁄≡1 (mod (2k+1)), (n≠2k) are Roman graphs, (2) the generalized Petersen graphs P(n,2k+1)( (mod 4) and ), P(n,1) (n⁄≡2 (mod 4)), P(n,3) ( (mod 4)) and P(11,3) are Roman graphs, and (3) the Cartesian product graphs are Roman graphs. 相似文献
5.
Sebastian M. Cioab? 《Linear algebra and its applications》2010,432(1):458-470
In this paper, we show that if the second largest eigenvalue of a d-regular graph is less than , then the graph is k-edge-connected. When k is 2 or 3, we prove stronger results. Let ρ(d) denote the largest root of x3-(d-3)x2-(3d-2)x-2=0. We show that if the second largest eigenvalue of a d-regular graph G is less than ρ(d), then G is 2-edge-connected and we prove that if the second largest eigenvalue of G is less than , then G is 3-edge-connected. 相似文献
6.
Florian Pfender 《Journal of Graph Theory》2010,64(3):206-209
For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t3(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t3(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010 相似文献
7.
Halina Bielak 《Discrete Mathematics》2009,309(22):6446-6449
P. Erdös, R.J. Faudree, C.C. Rousseau and R.H. Schelp [P. Erdös, R.J. Faudree, C.C. Rousseau, R.H. Schelp, The size Ramsey number, Period. Math. Hungar. 9 (1978) 145-161] studied the asymptotic behaviour of for certain graphs G,H. In this paper there will be given a lower bound for the diagonal size Ramsey number of Kn,n,n. The result is a generalization of a theorem for Kn,n given by P. Erdös and C.C. Rousseau [P. Erdös, C.C. Rousseau, The size Ramsey numbers of a complete bipartite graph, Discrete Math. 113 (1993) 259-262].Moreover, an open question for bounds for size Ramsey number of each n-regular graph of order n+t for t>n−1 is posed. 相似文献
8.
9.
《Discrete Mathematics》2019,342(10):2818-2820
10.
C. Picouleau 《Discrete Mathematics》2010,310(24):3646-3647
Mkrtchyan, Petrosyan, and Vardanyan made the following conjecture: Every graph G with Δ(G)−δ(G)≤1 has a maximum matching whose unsaturated vertices do not have a common neighbor. We disprove this conjecture. 相似文献
11.
12.
An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p≥3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete. 相似文献
13.
Tomoyuki Shirai 《Transactions of the American Mathematical Society》2000,352(1):115-132
Let be an infinite -regular graph and its line graph. We consider discrete Laplacians on and , and show the exact relation between the spectrum of and that of . Our method is also applicable to -semiregular graphs, subdivision graphs and para-line graphs.
14.
We exhibit a characteristic structure of the class of all regular graphs of degree d that stems from the spectra of their adjacency matrices. The structure has a fractal threadlike appearance. Points with coordinates given by the mean and variance of the exponentials of graph eigenvalues cluster around a line segment that we call a filar. Zooming-in reveals that this cluster splits into smaller segments (filars) labeled by the number of triangles in graphs. Further zooming-in shows that the smaller filars split into subfilars labeled by the number of quadrangles in graphs, etc. We call this fractal structure, discovered in a numerical experiment, a multifilar structure. We also provide a mathematical explanation of this phenomenon based on the Ihara-Selberg trace formula, and compute the coordinates and slopes of all filars in terms of Bessel functions of the first kind. 相似文献
15.
For any even integer k and any integer i, we prove that a (kr +i)-regular multigraph contains a k-factor if it contains no more than kr - 3k/2+ i + 2 cut edges, and this result is the best possible to guarantee the existence of k-factor in terms of the number of cut edges. We further give a characterization for k-factor free regular graphs. 相似文献
16.
Given a graph G and a subgraph H of G, let rb(G,H) be the minimum number r for which any edge-coloring of G with r colors has a rainbow subgraph H. The number rb(G,H) is called the rainbow number of H with respect to G. Denote as mK2 a matching of size m and as Bn,k the set of all the k-regular bipartite graphs with bipartition (X,Y) such that X=Y=n and k≤n. Let k,m,n be given positive integers, where k≥3, m≥2 and n>3(m−1). We show that for every GBn,k, rb(G,mK2)=k(m−2)+2. We also determine the rainbow numbers of matchings in paths and cycles. 相似文献
17.
《Discrete Mathematics》2022,345(11):113023
Let Γ be a graph with vertex set V, and let a and b be nonnegative integers. A subset C of V is called an -regular set in Γ if every vertex in C has exactly a neighbors in C and every vertex in has exactly b neighbors in C. In particular, -regular sets and -regular sets in Γ are called perfect codes and total perfect codes in Γ, respectively. A subset C of a group G is said to be an -regular set of G if there exists a Cayley graph of G which admits C as an -regular set. In this paper we prove that, for any generalized dihedral group G or any group G of order 4p or pq for some primes p and q, if a nontrivial subgroup H of G is a -regular set of G, then it must also be an -regular set of G for any and such that a is even when is odd. A similar result involving -regular sets of such groups is also obtained in the paper. 相似文献
18.
A of a digraph with arcs is a bijection from the set of arcs of to . A labeling of is if no two vertices in have the same vertex-sum, where the vertex-sum of a vertex for a labeling is the sum of labels of all arcs entering minus the sum of labels of all arcs leaving . An orientation of a graph is if has an antimagic labeling. Hefetz et al. (2010) raised the question: Does every graph admit an antimagic orientation? It had been proved that every 2-regular graph with at most two odd components has an antimagic orientation. In this paper, we consider 2-regular graphs with more than two odd components. We show that every 2-regular graph with odd components has an antimagic orientation. And we show that each 2-regular graph with odd components admits an antimagic orientation if each odd component has at least vertices with . 相似文献
19.
We show that the Hamiltonicity of a regular graph G can be fully characterized by the numbers of blocks of consecutive ones in the binary matrix A+I, where A is the adjacency matrix of G, I is the unit matrix, and the blocks can be either linear or circular. Concretely, a k-regular graph G with girth g(G)?5 has a Hamiltonian circuit if and only if the matrix A+I can be permuted on rows such that each column has at most (or exactly) k-1 circular blocks of consecutive ones; and if the graph G is k-regular except for two (k-1)-degree vertices a and b, then there is a Hamiltonian path from a to b if and only if the matrix A+I can be permuted on rows to have at most (or exactly) k-1 linear blocks per column.Then we turn to the problem of determining whether a given matrix can have at most k blocks of consecutive ones per column by some row permutation. For this problem, Booth and Lueker gave a linear algorithm for k=1 [Proceedings of the Seventh Annual ACM Symposium on Theory of Computing, 1975, pp. 255-265]; Flammini et al. showed its NP-completeness for general k [Algorithmica 16 (1996) 549-568]; and Goldberg et al. proved the same for every fixed k?2 [J. Comput. Biol. 2 (1) (1995) 139-152]. In this paper, we strengthen their result by proving that the problem remains NP-complete for every constant k?2 even if the matrix is restricted to (1) symmetric, or (2) having at most three blocks per row. 相似文献
20.
M.I. Ostrovskii 《数学物理学报(B辑英文版)》2011,31(2):634-640
The first problem considered in this article reads: is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs? It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n 3 2 , where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n 3 2 . 相似文献