Disjoint long cycles in a graph

We prove that if G is a graph of order at least 2k with k ? 9 and the minimum degree of G is at least k + 1, then G contains two vertex-disjoint cycles of order at least k. Moreover, the condition on the minimum degree is sharp.     

On matching and total domination in graphs

A set M of edges of a graph G is a matching if no two edges in M are incident to the same vertex. A set S of vertices in G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The matching number is the maximum cardinality of a matching of G, while the total domination number of G is the minimum cardinality of a total dominating set of G. In this paper, we investigate the relationships between the matching and total domination number of a graph. We observe that the total domination number of every claw-free graph with minimum degree at least three is bounded above by its matching number, and we show that every k-regular graph with k?3 has total domination number at most its matching number. In general, we show that no minimum degree is sufficient to guarantee that the matching number and total domination number are comparable.     

On the number of components in 2-factors of claw-free graphs

In this paper, we prove that if a claw-free graph G with minimum degree δ?4 has no maximal clique of two vertices, then G has a 2-factor with at most (|G|-1)/4 components. This upper bound is best possible. Additionally, we give a family of claw-free graphs with minimum degree δ?4 in which every 2-factor contains more than n/δ components.     

Outer-2-independent domination in graphs

We initiate the study of outer-2-independent domination in graphs. An outer-2-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)?D has a neighbor in D and the maximum vertex degree of the subgraph induced by V(G)?D is at most one. The outer-2-independent domination number of a graph G is the minimum cardinality of an outer-2-independent dominating set of G. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We also prove the Vizing-type conjecture for outer-2-independent domination and disprove the Vizing-type conjecture for outer-connected domination.     

Domination, radius, and minimum degree

We prove sharp bounds concerning domination number, radius, order and minimum degree of a graph. In particular, we prove that if G is a connected graph of order n, domination number γ and radius r, then . Equality is achieved in the upper bound if, and only if, G is a path or a cycle on n vertices with n≡4(mod6). Further, if G has minimum degree δ≥3 and r≥6, then using a result due to Erdös, Pach, Pollack, and Tuza [P. Erdös, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree. J. Combin. Theory B 47 (1989), 73-79] we show that .     

Independence,irredundance, degrees and chromatic number in graphs

Let β(G) and IR(G) denote the independence number and the upper irredundance number of a graph G. We prove that in any graph of order n, minimum degree δ and maximum degree Δ≠0, IR(G)⩽n/(1+δ/Δ) and IR(G)−β(G)⩽((Δ−2)/2Δ)n. The two bounds are attained by arbitrarily large graphs. The second one proves a conjecture by Rautenbach related to the case Δ=3. When the chromatic number χ of G is less than Δ, it can be improved to IR(G)−β(G)⩽((χ−2)/2χ)n in any non-empty graph of order n⩾2.     

The structure of plane graphs with independent crossings and its applications to coloring problems

If a graph G has a drawing in the plane in such a way that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. In this paper, the structure of IC-planar graphs with minimum degree at least two or three is studied. By applying their structural results, we prove that the edge chromatic number of G is Δ if Δ ≥ 8, the list edge (resp. list total) chromatic number of G is Δ (resp. Δ + 1) if Δ ≥ 14 and the linear arboricity of G is ?Δ/2? if Δ ≥ 17, where G is an IC-planar graph and Δ is the maximum degree of G.     

Planar graphs with maximum degree 8 and without intersecting chordal 4-cycles are 9-totally colorable

The minimum number of colors needed to properly color the vertices and edges of a graph G is called the total chromatic number of G and denoted by χ’’ (G). It is shown that if a planar graph G has maximum degree Δ≥9, then χ’’ (G) = Δ + 1. In this paper, we prove that if G is a planar graph with maximum degree 8 and without intersecting chordal 4-cycles, then χ ’’(G) = 9.     

Tricyclic graphs with exactly two main eigenvalues

An eigenvalue of a graph G is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero. Let G ₀ be the graph obtained from G by deleting all pendant vertices and δ(G) the minimum degree of vertices of G. In this paper, all connected tricyclic graphs G with δ(G ₀) ≥ 2 and exactly two main eigenvalues are determined.     

Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight

A graph H is defined to be light in a family H of graphs if there exists a finite number φ(H,H) such that each G∈H which contains H as a subgraph, contains also a subgraph K≅H such that the Δ_G(K)≤φ(H,H). We study light graphs in families of polyhedral graphs with prescribed minimum vertex degree δ, minimum face degree ρ, minimum edge weight w and dual edge weight w^∗. For those families, we show that there exists a variety of small light cycles; on the other hand, we also present particular constructions showing that, for certain families, the spectrum of short cycles contains irregularly scattered cycles that are not light.     

Minimum degree, leaf number and traceability

Let G be a finite connected graph with minimum degree δ. The leaf number L(G) of G is defined as the maximum number of leaf vertices contained in a spanning tree of G. We prove that if δ ? 1/2 (L(G) + 1), then G is 2-connected. Further, we deduce, for graphs of girth greater than 4, that if δ ? 1/2 (L(G) + 1), then G contains a spanning path. This provides a partial solution to a conjecture of the computer program Graffiti.pc [DeLaViña and Waller, Spanning trees with many leaves and average distance, Electron. J. Combin. 15 (2008), 1–16]. For G claw-free, we show that if δ ? 1/2 (L(G) + 1), then G is Hamiltonian. This again confirms, and even improves, the conjecture of Graffiti.pc for this class of graphs.     

Regular separable graphs of minimum order with given diameter

A (d, c, v)-graph G is one which is regular of degree v and has diameter d and connectivity c. G is said to be minimum if it is of minimum order, i.e. has the minimumnumber of points; G is separable if c=1.In this paper, the minimum order of a (d, 1, v)-graph is determined and the construction of all minimum (d, 1, v)-graphs is described.     

Paired-Domination in Claw-Free Graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number, denoted by γ _pr (G), is the minimum cardinality of a paired-dominating set in G. In this paper we investigate the paired-domination number in claw-free graphs. Specifically, we show that γ _pr (G) ≤ (3n ? 1)/5 if G is a connected claw-free graph of order n with minimum degree at least three and that this bound is sharp.     

Sphericity, cubicity, and edge clique covers of graphs

The sphericity sph(G) of a graph G is the minimum dimension d for which G is the intersection graph of a family of congruent spheres in R^d. The edge clique cover number θ(G) is the minimum cardinality of a set of cliques (complete subgraphs) that covers all edges of G. We prove that if G has at least one edge, then sph(G)?θ(G). Our upper bound remains valid for intersection graphs defined by balls in the L_p-norm for 1?p?∞.     

An upper bound for the minimum rank of a graph

For a graph G of order n, the minimum rank of G is defined to be the smallest possible rank over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. We prove an upper bound for minimum rank in terms of minimum degree of a vertex is valid for many graphs, including all bipartite graphs, and conjecture this bound is true over for all graphs, and prove a related bound for all zero-nonzero patterns of (not necessarily symmetric) matrices. Most of the results are valid for matrices over any infinite field, but need not be true for matrices over finite fields.     

A class of antimagic join graphs

A labeling f of a graph G is a bijection from its edge set E(G) to the set {1, 2, . . . , |E(G)|}, which is antimagic if for any distinct vertices x and y, the sum of the labels on edges incident to x is different from the sum of the labels on edges incident to y. A graph G is antimagic if G has an f which is antimagic. Hartsfield and Ringel conjectured in 1990 that every connected graph other than K 2 is antimagic. In this paper, we show that if G 1 is an n-vertex graph with minimum degree at least r, and G 2 is an m-vertex graph with maximum degree at most 2r-1 (m ≥ n), then G1 ∨ G2 is antimagic.     

Graphs Having (2 mod d)-Cycles

It is known that if G is a graph with minimum degree δ at least d+1, then G has a cycle of length 2 mod d. We show that if G is also bipartite, then G has a cycle of length 2 mod 2d. Both these bounds are tight in terms of minimum degree. However, we show that if G is a graph with δ ≥ d and had neither K_d nor K_d,d as an induced subgraph, then G has a cycle of length 2 mod d. If G is also bipartite, then G has a cycle of length 2 mod 2d. If G is a 2-connected graph with δ ≥ d and is not congruent to K_d nor K_d,d' (for d' ≥ d) then G has a cycle of length 2 mod d. If G is also bipartite, then G has a cycle of length 2 mod 2d.     

On large light graphs in families of polyhedral graphs

A graph H is said to be light in a family H of graphs if each graph G∈H containing a subgraph isomorphic to H contains also an isomorphic copy of H such that each its vertex has the degree (in G) bounded above by a finite number φ(H,H) depending only on H and H. We prove that in the family of all 3-connected plane graphs of minimum degree 5 (or minimum face size 5, respectively), the paths with certain small graphs attached to one of its ends are light.     

Bounds on Randi? indices

The general Randi? index of a molecular graph G is the sum of [d(u)d(v)]^α over all edges uv∈G, where d(v) denotes the degree of the vertex v in G and α is an arbitrary number. When α=−1/2, it is called the Randi? index. Delorme et al. stated a best possible lower bound on the Randi? index of a triangle-free graph with given minimum degree. Their false proof was pointed out by Liu et al. In this note, we derive some sharp bounds on the general Randi? index which implies their lower bound for triangle-free graphs of order n with maximum degree at most n/4, and also prove it for triangle-free graphs with small minimum degree.     

On regular bipartite-preserving supergraphs

For a graphG with chromatic numberχ(G) ? 2 and maximum degree Δ(G), there exists anr-regular graphH, for everyr ? Δ(G), such thatG is an induced subgraph ofH and_χ(H) =_χ (G). In the case whereG is bipartite, the minimum order of such a graphH is determined.