On finding the core of a tree with a specified length

A core of a graph G is a path P in G that is central with respect to the property of minizining d(P) = Σ_υεV(G)d(υ, P), where d(υ, P) is the distance from vertex υ to path P. This paper explores some properties of a core of a specified length.     

Two applications of semi-stable graphs

A Michigan graph G on a vertex set V is called semi-stable if for some υ?V, Γ(G_υ) = Γ(G)_υ. It can be shown that all regular graphs are semi-stable and this fact is used to show (i) that if Γ(G) is doubly transitive then G = K_n or K?_n, and (ii) that Γ(G) can be recovered from Γ(G_υ). The second result is extended to the case of stable graphs.     

Subpancyclicity of line graphs and degree sums along paths

A graph is called subpancyclic if it contains a cycle of length ? for each ? between 3 and the circumference of the graph. We show that if G is a connected graph on n?146 vertices such that d(u)+d(v)+d(x)+d(y)>(n+10/2) for all four vertices u,v,x,y of any path P=uvxy in G, then the line graph L(G) is subpancyclic, unless G is isomorphic to an exceptional graph. Moreover, we show that this result is best possible, even under the assumption that L(G) is hamiltonian. This improves earlier sufficient conditions by a multiplicative factor rather than an additive constant.     

The Connected Monophonic Number of a Graph

For a connected graph G = (V, E) of order at least two, a chord of a path P is an edge joining two non-adjacent vertices of P. A path P is called a monophonic path if it is a chordless path. A set S of vertices of G is a monophonic set of G if each vertex v of G lies on an x ? y monophonic path for some elements x and y in S. The minimum cardinality of a monophonic set of G is defined as the monophonic number of G, denoted by m(G). A connected monophonic set of G is a monophonic set S such that the subgraph G[S] induced by S is connected. The minimum cardinality of a connected monophonic set of G is the connected monophonic number of G and is denoted by m _c (G). We determine bounds for it and characterize graphs which realize these bounds. For any two vertices u and v in G, the monophonic distance d _m (u, v) from u to v is defined as the length of a longest u ? v monophonic path in G. The monophonic eccentricity e _m (v) of a vertex v in G is the maximum monophonic distance from v to a vertex of G. The monophonic radius rad _m G of G is the minimum monophonic eccentricity among the vertices of G, while the monophonic diameter diam _m G of G is the maximum monophonic eccentricity among the vertices of G. It is shown that for positive integers r, d and n ≥ 5 with r <  d, there exists a connected graph G with rad _m G =  r, diam _m G =  d and m _c (G) =  n. Also, if a,b and p are positive integers such that 2 ≤  a <  b ≤  p, then there exists a connected graph G of order p, m(G) =  a and m _c (G) =  b.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

A note on the weakly convex and convex domination numbers of a torus

The distanced_G(u,v) between two vertices u and v in a connected graph G is the length of the shortest (u,v) path in G. A (u,v) path of length d_G(u,v) is called a (u,v)-geodesic. A set X⊆V is called weakly convex in G if for every two vertices a,b∈X, exists an (a,b)-geodesic, all of whose vertices belong to X. A set X is convex in G if for all a,b∈X all vertices from every (a,b)-geodesic belong to X. The weakly convex domination number of a graph G is the minimum cardinality of a weakly convex dominating set of G, while the convex domination number of a graph G is the minimum cardinality of a convex dominating set of G. In this paper we consider weakly convex and convex domination numbers of tori.     

Eigenvalues of a graph and its imbeddings

A graph H is imbedded in a graph G if a subset of the vertices of G determines a subgraph isomorphic to H. If λ(G) is the least eigenvalue of G and k_R(H) = lim sup_d→∞ {λ(G)| H imbedded in G; G regular and connected; diam(G) > d; deg(G) > d}, then λ(H) ? 2 ≤ k_R(H) ≤ λ(H) with these bounds being the best possible. Given a graph H, there exist arbitrarily large families of isospectral graphs such that H can be imbedded in each member of the family.     

Some graft transformations and its applications on the distance spectral radius of a graph

Let D(G)=(d_i,j)_n×n denote the distance matrix of a connected graph G with order n, where d_ij is equal to the distance between v_i and v_j in G. The largest eigenvalue of D(G) is called the distance spectral radius of graph G, denoted by ?(G). In this paper, some graft transformations that decrease or increase ?(G) are given. With them, for the graphs with both order n and k pendant vertices, the extremal graphs with the minimum distance spectral radius are completely characterized; the extremal graph with the maximum distance spectral radius is shown to be a dumbbell graph (obtained by attaching some pendant edges to each pendant vertex of a path respectively) when 2≤k≤n−2; for k=1,2,3,n−1, the extremal graphs with the maximum distance spectral radius are completely characterized.     

The Chartrand-Schuster conjecture: Graphs with unique distance trees are regular

Let G be a finite connected graph with no cut vertex. A distance tree T is a spanning tree of G which further satisfies the condition that for some vertex v, d_G(v, u) = d_T(v, u) for all u, where d_G(v, u) denotes the distance of u from v in the graph G. The conjecture that if all distance trees of G are isomorphic to each other then G is a regular graph, is settled affirmatively. The conjecture was made by Chartrand and Schuster.     

An upper bound on the domination number of a graph with minimum degree 2

A set S of vertices in a graph G is a dominating set of G if every vertex of V(G)?S is adjacent to some vertex in S. The minimum cardinality of a dominating set of G is the domination number of G, denoted as γ(G). Let P_n and C_n denote a path and a cycle, respectively, on n vertices. Let k₁(F) and k₂(F) denote the number of components of a graph F that are isomorphic to a graph in the family {P₃,P₄,P₅,C₅} and {P₁,P₂}, respectively. Let L be the set of vertices of G of degree more than 2, and let G−L be the graph obtained from G by deleting the vertices in L and all edges incident with L. McCuaig and Shepherd [W. McCuaig, B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989) 749-762] showed that if G is a connected graph of order n≥8 with δ(G)≥2, then γ(G)≤2n/5, while Reed [B.A. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996) 277-295] showed that if G is a graph of order n with δ(G)≥3, then γ(G)≤3n/8. As an application of Reed’s result, we show that if G is a graph of order n≥14 with δ(G)≥2, then .     

A note on the partition dimension of Cartesian product graphs

Let G = (V, E) be a connected graph. The distance between two vertices u, v ∈ V, denoted by d(u, v), is the length of a shortest u − v path in G. The distance between a vertex v ∈ V and a subset P ⊂ V is defined as , and it is denoted by d(v, P). An ordered partition {P₁, P₂, … , P_t} of vertices of a graph G, is a resolving partition of G, if all the distance vectors (d(v, P₁), d(v, P₂), … , d(v, P_t)) are different. The partition dimension of G, denoted by pd(G), is the minimum number of sets in any resolving partition of G. In this article we study the partition dimension of Cartesian product graphs. More precisely, we show that for all pairs of connected graphs G, H, pd(G × H) ? pd(G) + pd(H) and pd(G × H) ? pd(G) + dim(H), where dim(H) denotes the metric dimension of H. Consequently, we show that pd(G × H) ? dim(G) + dim(H) + 1.     

An efficient condition for a graph to be Hamiltonian

Let G=(V,E) be a 2-connected simple graph and let d_G(u,v) denote the distance between two vertices u,v in G. In this paper, it is proved: if the inequality d_G(u)+d_G(v)?|V(G)|-1 holds for each pair of vertices u and v with d_G(u,v)=2, then G is Hamiltonian, unless G belongs to an exceptional class of graphs. The latter class is described in this paper. Our result implies the theorem of Ore [Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55]. However, it is not included in the theorem of Fan [New sufficient conditions for cycles in graph, J. Combin. Theory Ser. B 37 (1984) 221-227].     

What is the furthest graph from a hereditary property?

For a graph property P, the edit distance of a graph G from P, denoted E_P(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G to turn it into a graph satisfying P. What is the furthest graph on n vertices from P and what is the largest possible edit distance from P? Denote this maximal distance by ed(n,P). This question is motivated by algorithmic edge‐modification problems, in which one wishes to find or approximate the value of E_P(G) given an input graph G. A monotone graph property is closed under removal of edges and vertices. Trivially, for any monotone property, the largest edit distance is attained by a complete graph. We show that this is a simple instance of a much broader phenomenon. A hereditary graph property is closed under removal of vertices. We prove that for any hereditary graph property P, a random graph with an edge density that depends on P essentially achieves the maximal distance from P, that is: ed(n,P) = E_P(G(n,p(P))) + o(n²) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

On the domatic and the total domatic numbers of the 2-section graph of the order-interval hypergraph of a finite poset

Let P be a finite poset and H(P) be the hypergraph whose vertices are the points of P and whose edges are the maximal intervals in P. We study the domatic number d(G(P)) and the total domatic number d_t(G(P)) of the 2-section graph G(P) of H(P). For the subset P_l,u of P induced by consecutive levels of P, we give exact values of d(G(P_l,u)) when P is the chain product C_n1×C_n2. According to the values of l,u,n₁,n₂, the maximal domatic partition is exhibited. Moreover, we give some exact values or lower bounds for d(G(P∗Q)) and d_t(G(P_l,u)), when ∗ is the direct sum, the linear sum or the Cartesian product. Finally we show that the domatic number and the total domatic number problems in this class of graphs are NP-complete.     

Distance matrix polynomials of trees

Let G be a finite connected graph. If x and y are vertices of G, one may define a distance function d_G on G by letting d_G(x, y) be the minimal length of any path between x and y in G (with d_G(x, x) = 0). Thus, for example, d_G(x, y) = 1 if and only if {x, y} is an edge of G. Furthermore, we define the distance matrix D(G) for G to be the square matrix with rows and columns indexed by the vertex set of G which has d_G(x, y) as its (x, y) entry. In this paper we are concerned with properties of D(G) for the case in which G is a tree (i.e., G is acyclic). In particular, we precisely determine the coefficients of the characteristic polynomial of D(G). This determination is made by deriving surprisingly simple expressions for these coefficients as certain fixed linear combinations of the numbers of various subgraphs of G.     

A survey on labeling graphs with a condition at distance two

For positive integers k,d₁,d₂, a k-L(d₁,d₂)-labeling of a graph G is a function f:V(G)→{0,1,2,…,k} such that |f(u)-f(v)|?d_i whenever the distance between u and v is i in G, for i=1,2. The L(d₁,d₂)-number of G, λ_d1,d2(G), is the smallest k such that there exists a k-L(d₁,d₂)-labeling of G. This class of labelings is motivated by the code (or frequency) assignment problem in computer network. This article surveys the results on this labeling problem.     

Improvement on Brooks' chromatic bound for a class of graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and K_n+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K_1,3;K₅?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K₅?e can not be removed from the hypothesis. Moreover, for a graph G with none of K_1,3;K₅?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G).     

Gargano,Lewinter and Malerba问题的解

§1　IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1相似文献   

The entire graph of a bridgeless connected plane graph is hamiltonian

In this paper we show that the entire graph of a bridgeless connected plane graph is hamiltonian, and that the entire graph of a plane block is hamiltonian connected and vertex pancyclic. In addition, we show that in any block G which is not a circuit, given a vertex v of G and a circuit k of G, there is a path p, suspended in G, such that p is a path in k of length at least 1 and G ? E(p) ? V₀(G ? E(p)) is a block which includes v.     

On dominator colorings in graphs

A dominator coloring of a graph G is a proper coloring of G in which every vertex dominates every vertex of at least one color class. The minimum number of colors required for a dominator coloring of G is called the dominator chromatic number of G and is denoted by ?? _d (G). In this paper we present several results on graphs with ?? _d (G)?=???(G) and ?? _d (G)?=???(G) where ??(G) and ??(G) denote respectively the chromatic number and the domination number of a graph G. We also prove that if ??(G) is the Mycielskian of G, then ?? _d (G)?+?1?????? _d (??(G))?????? _d (G)?+?2.