Some Provably Hard Crossing Number Problems.
Some results on the Hadwiger numbers of graphs
Some Results on the Oberwolfach Problem. (Decomposition of Complete Graphs into Isomorphic Quadratic Factors). (Short Communication).
Some Results on the Oberwolfach Problem. (Decomposition of Completet Graphs into Isomorphic Quadratic Factors).
Some results on total domination in direct products of graphs
Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.
Some Sharp Bounds on the Negative Decision Number of Graphs
Let G = (V,E) be a graph. A function f : V → {-1,1} is called a bad function of G if ∑u∈NG(v) f(u) ≤ 1 for all v ∈ V where NG(v) denotes the set of neighbors of v in G. The negative decision number of G, introduced in [12], is the maximum value of ∑v∈V f(v) taken over all bad functions of G. In this paper, we present sharp upper bounds on the negative decision number of a graph in terms of its order, minimum degree, and maximum degree. We also establish a sharp Nordhaus-Gaddum-type inequality for...
Some totally 4-choosable multigraphs
It is proved that if G is multigraph with maximum degree 3, and every submultigraph of G has average degree at most 2(1/2) and is different from one forbidden configuration C⁺₄ with average degree exactly 2(1/2), then G is totally 4-choosable; that is, if every element (vertex or edge) of G is assigned a list of 4 colours, then every element can be coloured with a colour from its own list in such a way that no two adjacent or incident elements are coloured with the same colour. This shows that the...
Spanning trees of bounded degree.
Spanning trees with many leaves and average distance.
Spectral extrema for graphs: the Zarankiewicz problem.
Spectral radius and Hamiltonicity of graphs with large minimum degree
Let be a graph of order and the spectral radius of its adjacency matrix. We extend some recent results on sufficient conditions for Hamiltonian paths and cycles in . One of the main results of the paper is the following theorem: Let
Spectral saturation: inverting the spectral Turán theorem.
Square-root rule of two-dimensional bandwidth problem
The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root...
Square-root rule of two-dimensional bandwidth problem∗
The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root...
Steiner distance in graphs
Strong Chromatic Index Of Planar Graphs With Large Girth
Let Δ ≥ 4 be an integer. In this note, we prove that every planar graph with maximum degree Δ and girth at least 1 Δ+46 is strong (2Δ−1)-edgecolorable, that is best possible (in terms of number of colors) as soon as G contains two adjacent vertices of degree Δ. This improves [6] when Δ ≥ 6.
Structural properties of twin-free graphs.
Structure of the set of all minimal total dominating functions of some classes of graphs
In this paper we study some of the structural properties of the set of all minimal total dominating functions () of cycles and paths and introduce the idea of function reducible graphs and function separable graphs. It is proved that a function reducible graph is a function separable graph. We shall also see how the idea of function reducibility is used to study the structure of for some classes of graphs.
Structures algébriques généralisées des problèmes de cheminement dans les graphes
Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture.