Page 1 Next

Displaying 1 – 20 of 41

Showing per page

A Fiedler-like theory for the perturbed Laplacian

Israel Rocha, Vilmar Trevisan (2016)

Czechoslovak Mathematical Journal

The perturbed Laplacian matrix of a graph G is defined as L D = D - A , where D is any diagonal matrix and A is a weighted adjacency matrix of G . We develop a Fiedler-like theory for this matrix, leading to results that are of the same type as those obtained with the algebraic connectivity of a graph. We show a monotonicity theorem for the harmonic eigenfunction corresponding to the second smallest eigenvalue of the perturbed Laplacian matrix over the points of articulation of a graph. Furthermore, we use...

A note on face coloring entire weightings of plane graphs

Stanislav Jendrol, Peter Šugerek (2014)

Discussiones Mathematicae Graph Theory

Given a weighting of all elements of a 2-connected plane graph G = (V,E, F), let f(α) denote the sum of the weights of the edges and vertices incident with the face _ and also the weight of _. Such an entire weighting is a proper face colouring provided that f(α) ≠ f(β) for every two faces α and _ sharing an edge. We show that for every 2-connected plane graph there is a proper face-colouring entire weighting with weights 1 through 4. For some families we improved 4 to 3

A survey on combinatorial optimization in dynamic environments∗

Nicolas Boria, Vangelis T. Paschos (2011)

RAIRO - Operations Research

This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...

A survey on combinatorial optimization in dynamic environments∗

Nicolas Boria, Vangelis T. Paschos (2011)

RAIRO - Operations Research

This survey presents major results and issues related to the study of NPO problems in dynamic environments, that is, in settings where instances are allowed to undergo some modifications over time. In particular, the survey focuses on two complementary frameworks. The first one is the reoptimization framework, where an instance I that is already solved undergoes some local perturbation. The goal is then to make use of the information provided by the initial solution to compute a new solution. The...

An Implicit Weighted Degree Condition For Heavy Cycles

Junqing Cai, Hao Li, Wantao Ning (2014)

Discussiones Mathematicae Graph Theory

For a vertex v in a weighted graph G, idw(v) denotes the implicit weighted degree of v. In this paper, we obtain the following result: Let G be a 2-connected weighted graph which satisfies the following conditions: (a) The implicit weighted degree sum of any three independent vertices is at least t; (b) w(xz) = w(yz) for every vertex z ∈ N(x) ∩ N(y) with xy /∈ E(G); (c) In every triangle T of G, either all edges of T have different weights or all edges of T have the same weight. Then G contains...

Bootstrap clustering for graph partitioning

Philippe Gambette, Alain Guénoche (2011)

RAIRO - Operations Research - Recherche Opérationnelle

Given a simple undirected weighted or unweighted graph, we try to cluster the vertex set into communities and also to quantify the robustness of these clusters. For that task, we propose a new method, called bootstrap clustering which consists in (i) defining a new clustering algorithm for graphs, (ii) building a set of graphs similar to the initial one, (iii) applying the clustering method to each of them, making a profile (set) of partitions, (iv) computing a consensus partition for this profile,...

Bootstrap clustering for graph partitioning∗

Philippe Gambette, Alain Guénoche (2012)

RAIRO - Operations Research

Given a simple undirected weighted or unweighted graph, we try to cluster the vertex set into communities and also to quantify the robustness of these clusters. For that task, we propose a new method, called bootstrap clustering which consists in (i) defining a new clustering algorithm for graphs, (ii) building a set of graphs similar to the initial one, (iii) applying the clustering method to each of them, making a profile (set) of partitions, (iv) computing a consensus partition for this profile,...

Characterization of Line-Consistent Signed Graphs

Daniel C. Slilaty, Thomas Zaslavsky (2015)

Discussiones Mathematicae Graph Theory

The line graph of a graph with signed edges carries vertex signs. A vertex-signed graph is consistent if every circle (cycle, circuit) has positive vertex-sign product. Acharya, Acharya, and Sinha recently characterized line-consistent signed graphs, i.e., edge-signed graphs whose line graphs, with the naturally induced vertex signature, are consistent. Their proof applies Hoede’s relatively difficult characterization of consistent vertex-signed graphs. We give a simple proof that does not depend...

Cheeger inequalities for unbounded graph Laplacians

Frank Bauer, Matthias Keller, Radosław K. Wojciechowski (2015)

Journal of the European Mathematical Society

We use the concept of intrinsic metrics to give a new definition for an isoperimetric constant of a graph. We use this novel isoperimetric constant to prove a Cheeger-type estimate for the bottom of the spectrum which is nontrivial even if the vertex degrees are unbounded.

Digraphs are 2-weight choosable.

Khatirinejad, Mahdad, Naserasr, Reza, Newman, Mike, Seamone, Ben, Stevens, Brett (2011)

The Electronic Journal of Combinatorics [electronic only]

Graceful signed graphs

Mukti Acharya, Tarkeshwar Singh (2004)

Czechoslovak Mathematical Journal

A ( p , q ) -sigraph S is an ordered pair ( G , s ) where G = ( V , E ) is a ( p , q ) -graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E + and E - consist of m positive and n negative edges of G , respectively, where m + n = q . Given positive integers k and d , S is said to be ( k , d ) -graceful if the vertices of G can be labeled with distinct integers from the set { 0 , 1 , , k + ( q - 1 ) d } such that when each edge u v of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the...

Graceful signed graphs: II. The case of signed cycles with connected negative sections

Mukti Acharya, Tarkeshwar Singh (2005)

Czechoslovak Mathematical Journal

In our earlier paper [9], generalizing the well known notion of graceful graphs, a ( p , m , n ) -signed graph S of order p , with m positive edges and n negative edges, is called graceful if there exists an injective function f that assigns to its p vertices integers 0 , 1 , , q = m + n such that when to each edge u v of S one assigns the absolute difference | f ( u ) - f ( v ) | the set of integers received by the positive edges of S is { 1 , 2 , , m } and the set of integers received by the negative edges of S is { 1 , 2 , , n } . Considering the conjecture therein that all...

On composition of signed graphs

K. Shahul Hameed, K.A. Germina (2012)

Discussiones Mathematicae Graph Theory

A graph whose edges are labeled either as positive or negative is called a signed graph. In this article, we extend the notion of composition of (unsigned) graphs (also called lexicographic product) to signed graphs. We employ Kronecker product of matrices to express the adjacency matrix of this product of two signed graphs and hence find its eigenvalues when the second graph under composition is net-regular. A signed graph is said to be net-regular if every vertex has constant net-degree, namely,...

On •-Line Signed Graphs L•(S)

Deepa Sinha, Ayushi Dhama (2015)

Discussiones Mathematicae Graph Theory

A signed graph (or sigraph for short) is an ordered pair S = (Su,σ), where Su is a graph, G = (V,E), called the underlying graph of S and σ : E → {+,−} is a function from the edge set E of Su into the set {+,−}. For a sigraph S its •-line sigraph, L•(S) is the sigraph in which the edges of S are represented as vertices, two of these vertices are defined adjacent whenever the corresponding edges in S have a vertex in common, any such L-edge ee′ has the sign given by the product of the signs of the...

Currently displaying 1 – 20 of 41

Page 1 Next