Asymptotical estimation of some characteristics of finite graphs
Asymptotically optimal tree-packings in regular graphs.
Avoiding rainbow 2-connected subgraphs
While defining the anti-Ramsey number Erdős, Simonovits and Sós mentioned that the extremal colorings may not be unique. In the paper we discuss the uniqueness of the colorings, generalize the idea of their construction and show how to use it to construct the colorings of the edges of complete split graphs avoiding rainbow 2-connected subgraphs. These colorings give the lower bounds for adequate anti-Ramsey numbers.
-valuations of graphs
Bipartite diametrical graphs of diameter 4 and extreme orders.
Borsuk-Ulam type theorems
A generalization of the theorem of Bajmóczy and Bárány which in turn is a common generalization of Borsuk's and Radon's theorem is presented. A related conjecture is formulated.
Bounding the number of edges in permutation graphs.
Bounds for the number of meeting edges in graph partitioning
Let be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that admits a bipartition such that each vertex class meets edges of total weight at least , where is the total weight of edges of size and is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph (i.e., multi-hypergraph), we show that there exists a bipartition of such that each vertex class meets edges of total weight at least , where is the number...
Bounds for the rainbow connection number of graphs
An edge-coloured graph G is rainbow-connected if any two vertices are connected by a path whose edges have distinct colours. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow-connected. In this paper we show some new bounds for the rainbow connection number of graphs depending on the minimum degree and other graph parameters. Moreover, we discuss sharpness of some of these bounds.
Bounds of eigenvalues of -minor free graphs.
Bounds on the Signed 2-Independence Number in Graphs
Let G be a finite and simple graph with vertex set V (G), and let f V (G) → {−1, 1} be a two-valued function. If ∑x∈N|v| f(x) ≤ 1 for each v ∈ V (G), where N[v] is the closed neighborhood of v, then f is a signed 2-independence function on G. The weight of a signed 2-independence function f is w(f) =∑v∈V (G) f(v). The maximum of weights w(f), taken over all signed 2-independence functions f on G, is the signed 2-independence number α2s(G) of G. In this work, we mainly present upper bounds on α2s(G),...
Bounds on the Turán density of PG(3, 2).
Breaking symmetry on complete bipartite graphs of odd size.
Brève communication. Une caractérisation des graphes chromatiques minimaux sans sommet isolé
Brève communication. Une nouvelle méthode de marquage dans la recherche d'une chaîne de longueur maximale d'un arbre
Bridges and Hamiltonian circuits in planar graphs.
-saturated graphs of minimum size
Can Visibility Graphs Be Represented Compactly?.
Cardinality of a minimal forbidden graph family for reducible additive hereditary graph properties
An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let denote a class of all such properties. In the paper, we consider H-reducible over properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.
Centrosymmetric Graphs And A Lower Bound For Graph Energy Of Fullerenes
The energy of a molecular graph G is defined as the summation of the absolute values of the eigenvalues of adjacency matrix of a graph G. In this paper, an infinite class of fullerene graphs with 10n vertices, n ≥ 2, is considered. By proving centrosymmetricity of the adjacency matrix of these fullerene graphs, a lower bound for its energy is given. Our method is general and can be extended to other class of fullerene graphs.