A new Bartholdi zeta function of a digraph II

We introduce a new type of the Bartholdi zeta function of a digraph D. Furthermore, we define a new type of the Bartholdi L-function of D, and give a determinant expression of it. We show that this L-function of D is equal to the L-function of D defined in [H. Mizuno, I. Sato, A new Bartholdi zeta function of a digraph, Linear Algebra Appl. 423 (2007) 498-511]. As a corollary, we obtain a decomposition formula for a new type of the Bartholdi zeta function of a group covering of D by new Bartholdi L-functions of D.     

Scattering matrices of regular coverings of graphs

We give a decomposition formula for the determinant on the bond scattering matrix of a regular covering of G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we express the determinant on the bond scattering matrix of a regular covering of G by means of its L-functions.     

A survey of stratified domination in graphs

A graph G is 2-stratified if its vertex set is partitioned into two nonempty classes (each of which is a stratum or a color class). We color the vertices in one color class red and the other color class blue. Let F be a 2-stratified graph with one fixed blue vertex v specified. We say that F is rooted at v. The F-domination number of a graph G is the minimum number of red vertices of G in a red-blue coloring of the vertices of G such that for every blue vertex v of G, there is a copy of F in G rooted at v. In this paper, we survey recent results on the F-domination number for various 2-stratified graphs F.     

Pair lengths of product graphs

The pair length of a graph G is the maximum positive integer k, such that the vertex set of G can be partitioned into disjoint pairs {x,x^′}, such that d(x,x^′)?k for every x∈V(G) and x^′y^′ is an edge of G whenever xy is an edge. Chen asked whether the pair length of the cartesian product of two graphs is equal to the sum of their pair lengths. Our aim in this short note is to prove this result.     

Ramsey numbers for a disjoint union of good graphs

We give the Ramsey number for a disjoint union of some G-good graphs versus a graph G generalizing the results of Stahl (1975) [5] and Baskoro et al. (2006) [1] and the previous result of the author Bielak (2009) [2]. Moreover, a family of G-good graphs with s(G)>1 is presented.     

Edge-connectivity and edge-disjoint spanning trees

Given a graph G, for an integer c∈{2,…,|V(G)|}, define λ_c(G)=min{|X|:X⊆E(G),ω(G−X)≥c}. For a graph G and for an integer c=1,2,…,|V(G)|−1, define,

     

Covering graphs with matchings of fixed size

Let m be a positive integer and let G be a graph. We consider the question: can the edge set E(G) of G be expressed as the union of a set M of matchings of G each of which has size exactly m? If this happens, we say that G is [m]-coverable and we call M an [m]-covering of G. It is interesting to consider minimum[m]-coverings, i.e. [m]-coverings containing as few matchings as possible. Such [m]-coverings will be called excessive[m]-factorizations. The number of matchings in an excessive [m]-factorization is a graph parameter which will be called the excessive[m]-index and denoted by . In this paper we begin the study of this new parameter as well as of a number of other related graph parameters.     

A sufficient condition for pancyclability of graphs

Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by d_S(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with d_S(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with d_S(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).     

Chromatic characterization of biclique covers

A biclique B of a simple graph G is the edge-set of a complete bipartite subgraph of G. A biclique cover of G is a collection of bicliques covering the edge-set of G. Given a graph G, we will study the following problem: find the minimum number of bicliques which cover the edge-set of G. This problem will be called the minimum biclique cover problem (MBC). First, we will define the families of independent and dependent sets of the edge-set E(G) of G: F⊆E(G) will be called independent if there exists a biclique B⊆E(G) such that F⊆B, and will be called dependent otherwise. From our study of minimal dependent sets we will derive a 0-1 linear programming formulation of the following problem: find the maximum weighted biclique in a graph. This formulation may have an exponential number of constraints with respect to the number of nodes of G but we will prove that the continuous relaxation of this integer program can be solved in polynomial time. Finally we will also study continuous relaxation methods for the problem (MBC). This research was motivated by an open problem of Fishburn and Hammer.     

3-Factor-criticality in domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k-1 vertices. The structure of k-γ-critical graphs remains far from completely understood when k?3.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G) and is bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G). More generally, a graph is said to be k-factor-critical if G-S has a perfect matching for every set S of k vertices in G. In three previous papers [N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs, Discrete Math. 272 (2003) 5-15; N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs. II. Utilitas Math. 70 (2006) 11-32], we explored the toughness of 3-γ-critical graphs and some of their matching properties. In particular, we obtained some properties which are sufficient for a 3-γ-critical graph to be factor-critical and, respectively, bicritical. In the present work, we obtain similar results for k-factor-critical graphs when k=3.     

Spanning trails containing given edges

A graph G is Eulerian-connected if for any u and v in V(G), G has a spanning (u,v)-trail. A graph G is edge-Eulerian-connected if for any e^′ and e^″ in E(G), G has a spanning (e^′,e^″)-trail. For an integer r?0, a graph is called r-Eulerian-connected if for any X⊆E(G) with |X|?r, and for any , G has a spanning (u,v)-trail T such that X⊆E(T). The r-edge-Eulerian-connectivity of a graph can be defined similarly. Let θ(r) be the minimum value of k such that every k-edge-connected graph is r-Eulerian-connected. Catlin proved that θ(0)=4. We shall show that θ(r)=4 for 0?r?2, and θ(r)=r+1 for r?3. Results on r-edge-Eulerian connectivity are also discussed.     

A degree sum condition for graphs to be prism hamiltonian

Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ₃(G)≥n is prism hamiltonian. The degree sum condition “σ₃(G)≥n” is best possible.     

Minimal rankings and the arank number of a path

Given a graph G, a function f:V(G)→{1,2,…,k} is a k-ranking of G if f(u)=f(v) implies every u-v path contains a vertex w such that f(w)>f(u). A k-ranking is minimal if the reduction of any label greater than 1 violates the described ranking property. The arank number of a graph, denoted ψ_r(G), is the largest k such that G has a minimal k-ranking. We present new results involving minimal k-rankings of paths. In particular, we determine ψ_r(P_n), a problem posed by Laskar and Pillone in 2000.     

Partitioning graphs into complete and empty graphs

Given integers j and k and a graph G, we consider partitions of the vertex set of G into j+k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j,k)-graph. For a fixed j and k we consider the maximum order n where every graph of order n is a (j,k)-graph. The split-chromatic number of G is the minimum j where G is a (j,j)-graph. Further, the cochromatic number is the minimum j+k where G is a (j,k)-graph. We examine some relations between cochromatic, split-chromatic and chromatic numbers. We also consider some computational questions related to chordal graphs and cographs.     

Edge-deletable IM-extendable graphs with minimum number of edges

A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅K_k+2,k+2, or k=4r−2 for some integer r≥3 and G≅C₅[N_2r], where N_2r is the empty graph on 2r vertices and C₅[N_2r] is the graph obtained from C₅ by replacing each vertex with a graph isomorphic to N_2r.     

On the packing chromatic number of some lattices

For a positive integer k, a k-packing in a graph G is a subset A of vertices such that the distance between any two distinct vertices from A is more than k. The packing chromatic number of G is the smallest integer m such that the vertex set of G can be partitioned as V₁,V₂,…,V_m where V_i is an i-packing for each i. It is proved that the planar triangular lattice T and the three-dimensional integer lattice Z³ do not have finite packing chromatic numbers.     

Saturated packings and reduced coverings obtained by perturbing tilings

Let a normed space X possess a tiling T consisting of unit balls. We show that any packing P of X obtained by a small perturbation of T is completely translatively saturated; that is, one cannot replace finitely many elements of P by a larger number of unit balls such that the resulting arrangement is still a packing.In contrast with that, given a tiling T of Rⁿ with images of a convex body C under Euclidean isometries, there may exist packings P consisting of isometric images of C obtained from T by arbitrarily small perturbations which are no longer completely saturated. This means that there exists some positive integer k such that one can replace k−1 members of P by k isometric copies of C without violating the packing property. However, we quantify a tradeoff between the size of the perturbation and the minimal k such that the above phenomenon occurs.Analogous results are obtained for coverings.     

Linkability in iterated line graphs

We prove that for every graph H with the minimum degree δ?5, the third iterated line graph L³(H) of H contains as a minor. Using this fact we prove that if G is a connected graph distinct from a path, then there is a number k_G such that for every i?k_G the i-iterated line graph of G is -linked. Since the degree of Lⁱ(G) is even, the result is best possible.     

On the minimum real roots of the adjoint polynomial of a graph

For a graph G, we denote by h(G,x) the adjoint polynomial of G. Let β(G) denote the minimum real root of h(G,x). In this paper, we characterize all the connected graphs G with .     

On (d,1)-total numbers of graphs

A (d,1)-total labelling of a graph G assigns integers to the vertices and edges of G such that adjacent vertices receive distinct labels, adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least d. The span of a (d,1)-total labelling is the maximum difference between two labels. The (d,1)-total number, denoted , is defined to be the least span among all (d,1)-total labellings of G. We prove new upper bounds for , compute some for complete bipartite graphs K_m,n, and completely determine all for d=1,2,3. We also propose a conjecture on an upper bound for in terms of the chromatic number and the chromatic index of G.