Search

Abstract: A set S of vertices in a graph G is said to be an edge-dominating set if every edge in G is incident with a vertex in S. A cycle in G is said to be a dominating cycle if its vertex set is an edge-dominating set. Nash-Williams [Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, Studies in Pure Mathematics, Academic Press, London, 1971, pp. 157–183] has proved that every longest cycle in a 2-connected graph of order n and minimum degree at least is a dominating cycle. In this paper, we prove that for a prescribed positive integer k, under the same minimum degree condition, if n is sufficiently large and if we take k disjoint cycles so that they contain as many vertices as possible, then these cycles form an edge-dominating set. Nash-Williams’ Theorem corresponds to the case of of this result. [Copyright &y& Elsevier]

Abstract: For a pair of vertices x and y in a graph G, we denote by the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and for each neighbor of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by . In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of . [Copyright &y& Elsevier]

A graph G is said to be n-factor-critical if G−T has a perfect matching for every T⊂V(G) with |T|=n. For a vertex x of a graph G, local completion of G at x is the operation of joining every pair of nonadjacent vertices in NG(x). For a property P of graphs, a vertex x in a graph G is said to be P-eligible if the subgraph of G induced by NG(x) satisfies P but it is not complete. For a graph G, a graph H is said to be a P-closure of G if there exists a series of graphs G=G0,G1,…,Gr=H such that Gi is obtained from Gi−1 by local completion at some P-eligible vertex in Gi−1 and H=Gr has no P-eligible vertex. In this paper, we investigate the relation between factor-criticality and a P-closure, where P is a bounded independence number or a bounded domination number. [Copyright &y& Elsevier]

As a method of sharing a secret, e.g., a secret key, Shamir's (k, n) threshold method is well known. However, Shamir's method has a problem in that general access structures cannot be realized. This paper shows that by providing the trustees with several information data concerning the distributed information of the (k, n) threshold method, any access structure can be realized. The update with the change of the secret trustees and the relation to the threshold graph are also discussed. [ABSTRACT FROM AUTHOR]

Let H be a set of connected graphs, each of which has order at least three, and suppose that there exist infinitely many connected H‐free graphs of minimum degree at least  two and all except for finitely many of them have a 2‐factor. In [J. Graph Theory, 64 (2010), 250–266], we proved that if |H|≤3, then one of the members in H is a star. In this article, we determine the remaining members of H and hence give a complete characterization of the pairs and triples of forbidden subgraphs. [ABSTRACT FROM AUTHOR]

Abstract: In 1960 Ore proved the following theorem: Let G be a graph of order n. If for every pair of nonadjacent vertices u and , then G is hamiltonian. In this note we strengthen Ore''s theorem as follows: we determine the maximum number of pairs of nonadjacent vertices that can have degree sum less than n (i.e. violate Ore''s condition) but still imply that the graph is hamiltonian. Some other sufficient conditions (i.e. Fan''s condition) for hamiltonian graphs are strengthened as well. [Copyright &y& Elsevier]

The Chva´tal-Erdo˝s theorem says that a 2-connected graph with α(G)⩽κ(G) is hamiltonian. We extend this theorem for triangle-free graphs. We prove that if G is a 2-connected triangle-free graph of order n with α(G)⩽2κ(G)−2, then every longest cycle in G is dominating, and G has a cycle of length at least min{n−α(G)+κ(G),n}. [Copyright &y& Elsevier]

A graph G is said to be equimatchable if every matching in G extends to (i.e., is a subset of) a maximum matching. In this paper, we use the Gallai–Edmonds decomposition theory for matchings to determine the equimatchable members of two important graph classes. We find that there are precisely 23 3-connected planar graphs (i.e., 3-polytopes) which are equimatchable and that there are only two cubic equimatchable graphs. [Copyright &y& Elsevier]

Abstract: In this paper, we study the relationship between forbidden subgraphs and the existence of a matching. Let be a set of connected graphs, each of which has three or more vertices. A graph G is said to be -free if no graph in is an induced subgraph of G. We completely characterize the set such that every connected -free graph of sufficiently large even order has a perfect matching in the following cases. [(1)] Every graph in is triangle-free. [(2)] consists of two graphs (i.e. a pair of forbidden subgraphs). A matching M in a graph of odd order is said to be a near-perfect matching if every vertex of G but one is incident with an edge of M. We also characterize such that every -free graph of sufficiently large odd order has a near-perfect matching in the above cases. [Copyright &y& Elsevier]

Abstract: In this note, we consider a minimum degree condition for a hamiltonian graph to have a 2-factor with two components. Let G be a graph of order . Dirac''s theorem says that if the minimum degree of G is at least , then G has a hamiltonian cycle. Furthermore, Brandt et al. [J. Graph Theory 24 (1997) 165–173] proved that if , then G has a 2-factor with two components. Both theorems are sharp and there are infinitely many graphs G of odd order and minimum degree which have no 2-factor. However, if hamiltonicity is assumed, we can relax the minimum degree condition for the existence of a 2-factor with two components. We prove in this note that a hamiltonian graph of order and minimum degree at least has a 2-factor with two components. [Copyright &y& Elsevier]