Displaying similar documents to “Variable neighborhood search for extremal graphs. 17. Further conjectures and results about the index”

Relations between the domination parameters and the chromatic index of a graph

Włodzimierz Ulatowski (2009)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we show upper bounds for the sum and the product of the lower domination parameters and the chromatic index of a graph. We also present some families of graphs for which these upper bounds are achieved. Next, we give a lower bound for the sum of the upper domination parameters and the chromatic index. This lower bound is a function of the number of vertices of a graph and a new graph parameter which is defined here. In this case we also characterize graphs for which a respective...

The Distance Magic Index of a Graph

Aloysius Godinho, Tarkeshwar Singh, S. Arumugam (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph of order n and let S be a set of positive integers with |S| = n. Then G is said to be S-magic if there exists a bijection ϕ : V (G) → S satisfying ∑x∈N(u) ϕ(x) = k (a constant) for every u ∈ V (G). Let α(S) = max{s : s ∈ S}. Let i(G) = min α(S), where the minimum is taken over all sets S for which the graph G admits an S-magic labeling. Then i(G) − n is called the distance magic index of the graph G. In this paper we determine the distance magic index of trees and complete...

Generalized outerplanar index of a graph

Zahra Barati (2018)

Czechoslovak Mathematical Journal

Similarity:

We define the generalized outerplanar index of a graph and give a full characterization of graphs with respect to this index.

Pₘ-saturated bipartite graphs with minimum size

Aneta Dudek, A. Paweł Wojda (2004)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is said to be H-saturated if G is H-free i.e., (G has no subgraph isomorphic to H) and adding any new edge to G creates a copy of H in G. In 1986 L. Kászonyi and Zs. Tuza considered the following problem: for given m and n find the minimum size sat(n;Pₘ) of Pₘ-saturated graph of order n. They gave the number sat(n;Pₘ) for n big enough. We deal with similar problem for bipartite graphs.

On the Maximum and Minimum Sizes of a Graph with Givenk-Connectivity

Yuefang Sun (2017)

Discussiones Mathematicae Graph Theory

Similarity:

The concept of k-connectivity κk(G), introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. For an integer k ≥ 2, the k-connectivity of a connected graph G with order n ≥ k is the smallest number of vertices whose removal from G produces a graph with at least k components or a graph with fewer than k vertices. In this paper, we get a sharp upper bound for the size of G with κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3; moreover, the unique...

Spectral characterization of multicone graphs

Jianfeng Wang, Haixing Zhao, Qiongxiang Huang (2012)

Czechoslovak Mathematical Journal

Similarity:

A multicone graph is defined to be the join of a clique and a regular graph. Based on Zhou and Cho's result [B. Zhou, H. H. Cho, Remarks on spectral radius and Laplacian eigenvalues of a graph, Czech. Math. J. 55 (130) (2005), 781–790], the spectral characterization of multicone graphs is investigated. Particularly, we determine a necessary and sufficient condition for two multicone graphs to be cospectral graphs and investigate the structures of graphs cospectral to a multicone graph....

α-Labelings of a Class of Generalized Petersen Graphs

Anna Benini, Anita Pasotti (2015)

Discussiones Mathematicae Graph Theory

Similarity:

An α-labeling of a bipartite graph Γ of size e is an injective function f : V (Γ) → {0, 1, 2, . . . , e} such that {|ƒ(x) − ƒ(y)| : [x, y] ∈ E(Γ)} = {1, 2, . . . , e} and with the property that its maximum value on one of the two bipartite sets does not reach its minimum on the other one. We prove that the generalized Petersen graph PSn,3 admits an α-labeling for any integer n ≥ 1 confirming that the conjecture posed by Vietri in [10] is true. In such a way we obtain an infinite class...

Bounds on the Signed 2-Independence Number in Graphs

Lutz Volkmann (2013)

Discussiones Mathematicae Graph Theory

Similarity:

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...