首页 | 本学科首页 官方微博 | 高级检索

共查询到18条相似文献，搜索用时 292 毫秒
1.
Given graphs G_1 and G_2, we define a graph operation on G_1 and G_2,namely the SSG-vertex join of G_1 and G_2, denoted by G_1★ G_2. Let S(G) be the subdivision graph of G. The SSG-vertex join G_1★G_2 is the graph obtained from S(G_1) and S(G_2) by joining each vertex of G_1 with each vertex of G_2. In this paper, when G_i(i = 1, 2) is a regular graph, we determine the normalized Laplacian spectrum of G_1★ G_2. As applications, we construct many pairs of normalized Laplacian cospectral graphs, the normalized Laplacian energy, and the degree Kirchhoff index of G_1★G_2.  相似文献

2.
Let G be a simple graph. We first show that ■, where δiand di denote the i-th signless Laplacian eigenvalue and the i-th degree of vertex in G, respectively.Suppose G is a simple and connected graph, then some inequalities on the distance signless Laplacian eigenvalues are obtained by deleting some vertices and some edges from G. In addition, for the distance signless Laplacian spectral radius ρQ(G), we determine the extremal graphs with the minimum ρQ(G) among the trees with given diameter, the unicyclic and bicyclic graphs with given girth, respectively.  相似文献

3.
A graph is 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. In this paper, it is shown that each 1-planar graph with minimum degree 7 contains a copy of K2∨(K1∪K2) with all vertices of degree at most 12. In addition, we also prove the existence of a graph K1∨(K1∪K2 ) with relatively small degree vertices in 1-planar graphs with minimum degree at least 6.  相似文献

4.
5.
A graph property is any class of graphs that is closed under isomorphisms. A graph property P is hereditary if it is closed under taking subgraphs; it is compositive if for any graphs G1, G2 ∈ P there exists a graph G ∈ P containing both G1 and G2 as subgraphs. Let H be any given graph on vertices v1, . . . , vn, n ≥ 2. A graph property P is H-factorizable over the class of graph properties P if there exist P 1 , . . . , P n ∈ P such that P consists of all graphs whose vertex sets can be partitioned into n parts, possibly empty, satisfying: 1. for each i, the graph induced by the i-th non-empty partition part is in P i , and 2. for each i and j with i = j, there is no edge between the i-th and j-th parts if vi and vj are non-adjacent vertices in H. If a graph property P is H-factorizable over P and we know the graph properties P 1 , . . . , P n , then we write P = H [ P 1 , . . . , P n ]. In such a case, the presentation H[ P 1 , . . . , P n ] is called a factorization of P over P. This concept generalizes graph homomorphisms and (P 1 , . . . , P n )-colorings. In this paper, we investigate all H-factorizations of a graph property P over the class of all hered- itary compositive graph properties for finite graphs H. It is shown that in many cases there is exactly one such factorization.  相似文献

6.
An edge colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. A vertex colored graph G is vertex rainbow connected if any two vertices are connected by a path whose internal vertices have distinct colors. The vertex rainbow connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G vertex rainbow connected. In 2011, Kemnitz and Schiermeyer considered graphs with rc(G) = 2.We investigate graphs with rvc(G) = 2. First, we prove that rvc(G) 2 if |E(G)|≥n-22 + 2, and the bound is sharp. Denote by s(n, 2) the minimum number such that, for each graph G of order n, we have rvc(G) 2provided |E(G)|≥s(n, 2). It is proved that s(n, 2) = n-22 + 2. Next, we characterize the vertex rainbow connection numbers of graphs G with |V(G)| = n, diam(G)≥3 and clique number ω(G) = n- s for 1≤s≤4.  相似文献

7.
In this paper,for the purpose of measuring the non-self-centrality extent of non-selfcentered graphs,a novel eccentricity-based invariant,named as non-self-centrality number(NSC number for short),of a graph G is defined as follows:N(G)=∑v_i,v_j∈V(G)|e_i-e_j| where the summation goes over all the unordered pairs of vertices in G and e_i is the eccentricity of vertex v_i in G,whereas the invariant will be called third Zagreb eccentricity index if the summation only goes over the adjacent vertex pairs of graph G.In this paper,we determine the lower and upper bounds on N(G) and characterize the corresponding graphs at which the lower and upper bounds are attained.Finally we propose some attractive research topics for this new invariant of graphs.  相似文献

8.
A graph is symmetric or 1-regular if its automorphism group is transitive or regular on the arc set of the graph, respectively. We classify the connected pentavalent symmetric graphs of order 2p~3 for each prime p. All those symmetric graphs appear as normal Cayley graphs on some groups of order 2p~3 and their automorphism groups are determined. For p = 3, no connected pentavalent symmetric graphs of order 2p~3 exist. However, for p = 2 or 5, such symmetric graph exists uniquely in each case. For p 7, the connected pentavalent symmetric graphs of order 2p~3 are all regular covers of the dipole Dip5 with covering transposition groups of order p~3, and they consist of seven infinite families; six of them are 1-regular and exist if and only if 5 |(p- 1), while the other one is 1-transitive but not 1-regular and exists if and only if 5 |(p ± 1). In the seven infinite families, each graph is unique for a given order.  相似文献

9.

10.
In 2006, Sullivan stated the conjectures:(1) every oriented graph has a vertex x such that d~(++)(x) ≥ d~-(x);(2) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 d~-(x);(3) every oriented graph has a vertex x such that d~(++)(x) + d~+(x) ≥ 2 · min{d~+(x), d~-(x)}. A vertex x in D satisfying Conjecture(i) is called a Sullivan-i vertex, i = 1, 2, 3. A digraph D is called quasi-transitive if for every pair xy, yz of arcs between distinct vertices x, y, z, xz or zx("or" is inclusive here) is in D. In this paper, we prove that the conjectures hold for quasi-transitive oriented graphs, which is a superclass of tournaments and transitive acyclic digraphs. Furthermore, we show that a quasi-transitive oriented graph with no vertex of in-degree zero has at least three Sullivan-1 vertices and a quasi-transitive oriented graph has at least three Sullivan-3 vertices unless it belongs to an exceptional class of quasitransitive oriented graphs. For Sullivan-2 vertices, we show that an extended tournament, a subclass of quasi-transitive oriented graphs and a superclass of tournaments, has at least two Sullivan-2 vertices unless it belongs to an exceptional class of extended tournaments.  相似文献

11.

12.

Let d be the smallest generator number of a finite p-group P and let Md（P） = {P1,...,Pd} be a set of maximal subgroups of P such that ∩di=1 Pi = Φ（P）. In this paper, we study the structure of a finite group G under the assumption that every member in Md（Gp） is S-semipermutable in G for each prime divisor p of ｜G｜ and a Sylow p-subgroup Gp of G.  相似文献

13.

14.

15.

16.

17.

18.