共查询到20条相似文献,搜索用时 15 毫秒
1.
Su Jianji 《Journal of Graph Theory》1995,20(3):287-295
Madar conjectured that every k-critical n-connected non-complete graph G has (2k + 2) pairwise disjoint fragments. We show that Mader's conjecture holds if the order of G is greater than (k + 2)n. From this, it implies that two other conjectures on k-critical n-connected graphs posed by Entringer, Slater, and Mader also hold if the cardinality of the graphs is large. © 1995 John Wiley & Sons, Inc. 相似文献
2.
Carsten Flotow 《Journal of Graph Theory》1997,24(4):323-330
The main theorem of this paper gives a forbidden induced subgraph condition on G that is sufficient for chordality of Gm. This theorem is a generalization of a theorem of Balakrishnan and Paulraja who had provided this only for m = 2. We also give a forbidden subgraph condition on G that is sufficient for chordality of G2m. Similar conditions on G that are sufficient for Gm being an interval graph are also obtained. In addition it is easy to see, that no family of forbidden (induced) subgraphs of G is necessary for Gm being chordal or interval graph. © 1997 John Wiley & Sons, Inc. 相似文献
3.
The distinguishing number D(G) of a graph is the least integer d such that there is a d‐labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G ≠ K2, K3 with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #N17] on powers of prime graphs, and results of Klav?ar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G □ H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2|H| ? |H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006 相似文献
4.
The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M1 and M2 of M(G) are adjacent if and only if |M1 − M2| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998 相似文献
5.
Let G be a finite simple graph and I(G) denote the corresponding edge ideal. For all \(s \ge 1\), we obtain upper bounds for \({\text {reg}}(I(G)^s)\) for bipartite graphs. We then compare the properties of G and \(G'\), where \(G'\) is the graph associated with the polarization of the ideal \((I(G)^{s+1} : e_1\cdots e_s)\), where \(e_1,\cdots , e_s\) are edges of G. Using these results, we explicitly compute \({\text {reg}}(I(G)^s)\) for several subclasses of bipartite graphs. 相似文献
6.
Augustine M. Moshi 《Journal of Graph Theory》1989,13(5):527-536
Let G = (V,E) be an undirected graph. A subset F of E is a matching cutset of G if no two edges of F are incident with the same point, and G-F has more components than G. Chv?atal [2] proved that it is NP-complete to recognize graphs with a matching cutset even if the input is restricted to graphs with maximum degree 4. We prove the following: (a) Every connected graph with maximum degree ?3 and on more than 7 points has a matching cutset. (In particular, there are precisely two connected cubic graphs without a matching cutset). (b) Line graphs with a matching cutset can be recognized in O(|E|) time. (c) Graphs without a chordless circuit of length 5 or more that have a matching cutset can be recognized in O(|V||E|3) time. 相似文献
7.
Graphs are important structures to model complex relationships such as chemical compounds, proteins, geometric or hierarchical parts, and XML documents. Given a query graph, indexing has become a necessity to retrieve similar graphs quickly from large databases. We propose a novel technique for indexing databases, whose entries can be represented as graph structures. Our method starts by representing the topological structure of a graph as well as that of its subgraphs as vectors in which the components correspond to the sorted laplacian eigenvalues of the graph or subgraphs. By doing a nearest neighbor search around the query spectra, similar but not necessarily isomorphic graphs are retrieved. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
8.
We investigate the relationship between projectivity and the structure of maximal independent sets in powers of circular graphs, Kneser graphs and truncated simplices. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 162–171, 2002 相似文献
9.
A fundamental problem in computational biology is the phylogeny reconstruction for a set of specific organisms. One of the graph theoretical approaches is to construct a similarity graph on the set of organisms where adjacency indicates evolutionary closeness, and then to reconstruct a phylogeny by computing a tree interconnecting the organisms such that leaves in the tree are labeled by the organisms and every organism appears as a leaf in the tree. The similarity graph is simple and undirected. For any pair of adjacent organisms in the similarity graph, their distance in the output tree, which is measured by the number of edges on the path connecting them, must be less than some pre-specified bound. This is known as the problem of recognizing leaf powers and computing leaf roots. Graphs that are leaf powers are known to be chordal. It is shown in this paper that all strictly chordal graphs are leaf powers and a linear time algorithm is presented to compute a leaf root for any given strictly chordal graph. An intermediate root-and-power problem, the Steiner root problem, is also examined. 相似文献
10.
11.
We give a closed formula for Lovász’s theta number of the powers of cycle graphs C k d?1 and of their complements, the circular complete graphs K k/d . As a consequence, we establish that the circular chromatic number of a circular perfect graph is computable in polynomial time. We also derive an asymptotic estimate for the theta number of C k d . 相似文献
12.
13.
A graph is chordal if every cycle of length strictly greater than three has a chord. A necessary and sufficient condition is given for all powers of a chordal graph to be chordal. In addition, it is shown that for connected chordal graphs the center (the set of all vertices with minimum eccentricity) always induces a connected subgraph. A relationship between the radius and diameter of chordal graphs is also established. 相似文献
14.
Given a positive integer and a graph with degree sequence , we define . Caro and Yuster introduced a Turán-type problem for : Given a positive integer and a graph , determine the function , which is the maximum value of taken over all graphs on vertices that do not contain as a subgraph. Clearly, , where denotes the classical Turán number. Caro and Yuster determined the function for sufficiently large , where and denotes the path on vertices. In this paper, we generalise this result and determine for sufficiently large , where and is a linear forest. We also determine , where is a star forest; and , where is a broom graph with diameter at most six. 相似文献
15.
16.
E. A. Palyutin 《Journal of Mathematical Sciences》2010,167(6):825-840
The basic result of the work is the theorem that if an axiomatizable class K of structures is closed under reduced powers by the Frechet filter and it has a stable noncommutative theory, then the class
of all graphs is interpretable in the class K. 相似文献
17.
Jií Fink 《European Journal of Combinatorics》2009,30(7):1624
Kreweras’ conjecture [G. Kreweras, Matchings and hamiltonian cycles on hypercubes, Bull. Inst. Combin. Appl. 16 (1996) 87–91] asserts that every perfect matching of the hypercube Qd can be extended to a Hamiltonian cycle of Qd. We [Jiří Fink, Perfect matchings extend to hamilton cycles in hypercubes, J. Combin. Theory Ser. B, 97 (6) (2007) 1074–1076] proved this conjecture but here we present a simplified proof.The matching graph of a graph G has a vertex set of all perfect matchings of G, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle of G. We show that the matching graph of a complete bipartite graph is bipartite if and only if n is even or n=1. We prove that is connected for n even and has two components for n odd, n≥3. We also compute distances between perfect matchings in . 相似文献
18.
Leaf powers are a graph class which has been introduced to model the problem of reconstructing phylogenetic trees. A graph G=(V,E) is called k-leaf power if it admits a k-leaf root, i.e., a tree T with leaves V such that uv is an edge in G if and only if the distance between u and v in T is at most k. Moroever, a graph is simply called leaf power if it is a k-leaf power for some k∈N. This paper characterizes leaf powers in terms of their relation to several other known graph classes. It also addresses the problem of deciding whether a given graph is a k-leaf power.We show that the class of leaf powers coincides with fixed tolerance NeST graphs, a well-known graph class with absolutely different motivations. After this, we provide the largest currently known proper subclass of leaf powers, i.e, the class of rooted directed path graphs.Subsequently, we study the leaf rank problem, the algorithmic challenge of determining the minimum k for which a given graph is a k-leaf power. Firstly, we give a lower bound on the leaf rank of a graph in terms of the complexity of its separators. Secondly, we use this measure to show that the leaf rank is unbounded on both the class of ptolemaic and the class of unit interval graphs. Finally, we provide efficient algorithms to compute 2|V|-leaf roots for given ptolemaic or (unit) interval graphs G=(V,E). 相似文献
19.
20.
For a non-zero real number α, let s α (G) denote the sum of the αth power of the non-zero Laplacian eigenvalues of a graph G. In this paper, we establish a connection between s α (G) and the first Zagreb index in which the Hölder’s inequality plays a key role. By using this result, we present a lot of bounds of s α (G) for a connected (molecular) graph G in terms of its number of vertices (atoms) and edges (bonds). We also present other two bounds for s α (G) in terms of connectivity and chromatic number respectively, which generalize those results of Zhou and Trinajsti? for the Kirchhoff index [B Zhou, N Trinajsti?. A note on Kirchhoff index, Chem. Phys. Lett., 2008, 455: 120–123]. 相似文献