共查询到20条相似文献,搜索用时 750 毫秒
1.
Sean McGuinness 《Combinatorica》1994,14(3):321-334
A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of ordern has at mostn 2/4 cliques. In this paper, we extend this result by showing that for any positive integerp, 3≤p any clique decomposisitioof a graph of ordern obtained by removing maximal cliques of order at leastp one by one until none remain, in which case the remaining edges are removed one by one, has at mostt p-1( n ) cliques. Heret p-1( n ) is the number of edges in the Turán graph of ordern, which has no complete subgraphs of orderp. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decompositionC of a graphG of ordern the sum over the number of vertices in each clique ofC is at mostn 2/2. We prove this conjecture forK 4-free graphs and show that in the case of equality forC andG there are only two possibilities:
- G?K n/2,n/2
- G is complete 3-partite, where each part hasn/3 vertices.
2.
《Discrete Applied Mathematics》1987,16(1):11-15
The vertices of a threshold graph G are partitioned into a clique K and an independent set I so that the neighborhoods of the vertices of I are totally ordered by inclusion. The question of whether G is hamiltonian is reduced to the case that K and I have the same size, say r, in which case the edges of K do not affect the answer and may be dropped from G, yielding a bipartite graph B. Let d1≤d2≤…≤dr and e1≤e2≤…≤er be the degrees in B of the vertices of I and K, respectively. For each q = 0, 1,…,r−1, denote by Sq the following system of inequalities: dj⩾j + 1, j = 1,2,…,q, ej⩾j + 1, j = 1, 2,…, r−1−1. Then the following conditions are equivalent:
- 1.(1) B is hamiltonian,
- 2.(2) Sq holds for some q = 0, 1,…, r−1,
- 3.(3) Sq holds for each q = 0, 1,…, r−1.
3.
Frédéric Maire 《Graphs and Combinatorics》1994,10(2-4):263-268
A graph istriangulated if it has no chordless cycle with at least four vertices (?k ≥ 4,C k ?G). These graphs Jhave been generalized by R. Hayward with theweakly triangulated graphs $(\forall k \geqslant 5,C_{k,} \bar C_k \nsubseteq G)$ . In this note we propose a new generalization of triangulated graphs. A graph G isslightly triangulated if it satisfies the two following conditions;
- G contains no chordless cycle with at least 5 vertices.
- For every induced subgraphH of G, there is a vertex inH the neighbourhood of which inH contains no chordless path of 4 vertices.
4.
Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that G ∈ F if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each G ∈ F, G is not Z 3-connected if and only if G is one of K 2,n?2, K 3,n?3, K 2,n?2 + , K 3,n?3 + or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240]. 相似文献
5.
Given a tree, T, consider one of its longest paths, PT, not necessarily unique. We define T to be m–distant if no vertices of T are a distance greater than m away from PT. We will show that all 3–distant graphs are graceful, providing they satisfy the following properties.
- 1.They have perfect matchings.
- 2.They can be constructed by attaching paths of length 2 to the vertices of a 1–distant tree (caterpillar), by the identification of their end vertices.
6.
The eccentric connectivity index \(\xi ^c(G)\) of a connected graph G is defined as \(\xi ^c(G) =\sum _{v \in V(G)}{deg(v) e(v)},\) where deg(v) is the degree of vertex v and e(v) is the eccentricity of v. The eccentric graph, \(G_e\), of a graph G has the same set of vertices as G, with two vertices u, v adjacent in \(G_e\) if and only if either u is an eccentric vertex of v or v is an eccentric vertex of u. In this paper, we obtain a formula for the eccentric connectivity index of the eccentric graph of a regular dendrimer. We also derive a formula for the eccentric connectivity index for the second iteration of eccentric graph of regular dendrimer. 相似文献
7.
The following Theorem is proved:Let K be a finitely generated field over its prime field. Then, for almost all e-tuples (σ)=(σ 1, …,σ e)of elements of the abstract Galois group G(K)of K we have:
- If e=1,then E tor(K(σ))is infinite. Morover, there exist infinitely many primes l such that E(K(σ))contains points of order l.
- If e≧2,then E tor(K(σ))is finite.
- If e≧1,then for every prime l, the group E(K(σ))contains only finitely many points of an l-power order.
8.
Ruy Fabila-Monroy David Flores-Peñaloza Clemens Huemer Ferran Hurtado Jorge Urrutia David R. Wood 《Graphs and Combinatorics》2012,28(3):365-380
For a graph G and integer k ≥ 1, we define the token graph F k (G) to be the graph with vertex set all k-subsets of V(G), where two vertices are adjacent in F k (G) whenever their symmetric difference is a pair of adjacent vertices in G. Thus vertices of F k (G) correspond to configurations of k indistinguishable tokens placed at distinct vertices of G, where two configurations are adjacent whenever one configuration can be reached from the other by moving one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs. 相似文献
9.
Let G be a connected graph with vertex set V(G) = {v1, v2,..., v n }. The distance matrix D(G) = (d ij )n×n is the matrix indexed by the vertices of G, where d ij denotes the distance between the vertices v i and v j . Suppose that λ1(D) ≥ λ2(D) ≥... ≥ λ n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra. 相似文献
10.
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. 相似文献
11.
A. V. Pyatkin 《Journal of Applied and Industrial Mathematics》2008,2(3):379-384
A graph G = (V,E) is an integral sum graph if there exists a labeling S(G) ? Z such that V = S(G) and every two distinct vertices u, υ ∈ V are adjacent if and only if u + υ ∈ V. A connected graph G = (V,E) is called unicyclic if |V| = |E|. In this paper two infinite series are constructed of unicyclic graphs that are not integral sum graphs. 相似文献
12.
In my talk, I will present some works done in the nineties on Laplacians on graphs: from eigenvalue problems to inverse problem for resistor networks. I will focus on the motivations and the main results as well as on the main ideas:
- •A differential topology point of view on the minor relation: a nice stratification associated to a finite graph Γ whose strata are associated to the minors of Γ
- •“Discrete” (graphs) versus “continuous” (Riemannian manifolds)
- •Stability of spectra with respect to singular limits: a finite dimensional theory of operators with domains (Von Neumann theory).
13.
V. V. Kabanov A. V. Mityanina 《Proceedings of the Steklov Institute of Mathematics》2014,285(1):78-90
For a given graph G, its line graph L(G) is defined as the graph with vertex set equal to the edge set of G in which two vertices are adjacent if and only if the corresponding edges of G have exactly one common vertex. A k-regular graph of diameter 2 on υ vertices is called a strictly Deza graph with parameters (υ, k, b, a) if it is not strongly regular and any two vertices have a or b common neighbors. We give a classification of strictly Deza line graphs. 相似文献
14.
15.
16.
A graph is said to be claw-free if it does not contain an induced subgraph isomorphic to K1,3. Let s and k be two integers with 0 ≤ s ≤ k and let G be a claw-free graph of order n. In this paper, we investigate clique partition problems in claw-free graphs. It is proved that if n ≥ 3s+4(k?s) and d(x)+d(y) ≥ n?2s+2k+1 for any pair of non-adjacent vertices x, y of G, then G contains s disjoint K3s and k ? s disjoint K4s such that all of them are disjoint. Moreover, the degree condition is sharp in some cases. 相似文献
17.
18.
A seagull in a graph is an induced three-vertex path. When does a graph G have k pairwise vertex-disjoint seagulls? This is NP-complete in general, but for graphs with no stable set of size three we give a complete solution. This case is of special interest because of a connection with Hadwiger’s conjecture which was the motivation for this research; and we deduce a unification and strengthening of two theorems of Blasiak [2] concerned with Hadwiger’s conjecture. Our main result is that a graph G (different from the five-wheel) with no three-vertex stable set contains k disjoint seagulls if and only if
- |V (G)|≥3k
- G is k-connected
- for every clique C of G, if D denotes the set of vertices in V (G)\C that have both a neighbour and a non-neighbour in C then |D|+|V (G)\C|≥2k, and
- the complement graph of G has a matching with k edges.
19.
Jiuying Dong 《Journal of Applied Mathematics and Computing》2010,34(1-2):485-493
The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ 2(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:
- Let k≥2 be an integer and G be a graph of order n≥3k, if σ 2(G)≥n+2k?2, then for any set of k distinct vertices v 1,…,v k , G has k vertex-disjoint cycles C 1,C 2,…,C k of length at most four such that v i ∈V(C i ) for all 1≤i≤k.
- Let k≥1 be an integer and G be a graph of order n≥3k, if σ 2(G)≥n+2k?2, then for any set of k distinct vertices v 1,…,v k , G has k vertex-disjoint cycles C 1,C 2,…,C k such that:
- v i ∈V(C i ) for all 1≤i≤k.
- V(C 1)∪???∪V(C k )=V(G), and
- |C i |≤4, 1≤i≤k?1.
20.
Mehdi Shabani Attar 《Archiv der Mathematik》2009,93(5):399-403
Let G be a nonabelian finite p-group. A longstanding conjecture asserts that G admits a noninner automorphism of order p. In this paper, we prove that if G satisfies one of the following conditions
- ${\mathrm{rank}(G'\cap Z(G))\neq \mathrm{rank}(Z(G))}$
- ${\frac{Z_{2}(G)}{Z(G)}}$ is cyclic
- C G (Z(Φ(G))) = Φ(G) and ${\frac{Z_{2}(G)\cap Z(\Phi(G))}{Z(G)} }$ is not elementary abelian of rank rs, where r = d(G) and s = rank (Z(G)),