1,720,970 research outputs found
On dynamic monopolies of graphs with general thresholds
No full textAbstractLet G be a graph and τ:V(G)→N be an assignment of thresholds to the vertices of G. A subset of vertices D is said to be dynamic monopoly (or simply dynamo) if the vertices of G can be partitioned into subsets D0,D1,…,Dk such that D0=D and for any i=1,…,k−1 each vertex v in Di+1 has at least t(v) neighbors in D0∪⋯∪Di. Dynamic monopolies are in fact modeling the irreversible spread of influence such as disease or belief in social networks. We denote the smallest size of any dynamic monopoly of G, with a given threshold assignment, by dyn(G). In this paper, we first define the concept of a resistant subgraph and show its relationship with dynamic monopolies. Then we obtain some lower and upper bounds for the smallest size of dynamic monopolies in graphs with different types of thresholds. Next we introduce dynamo-unbounded families of graphs and prove some related results. We also define the concept of a homogeneous society that is a graph with probabilistic thresholds satisfying some conditions and obtain a bound for the smallest size of its dynamos. Finally, we consider dynamic monopoly of line graphs and obtain some bounds for their sizes and determine the exact values in some special cases
More relations between -labeling and Hamiltonian paths with emphasis on line graph of bipartite multigraphs
Get PDFThis paper deals with the -labeling and -coloring of simple
graphs. A -labeling of a graph is any labeling of the vertices of
with different labels such that any two adjacent vertices receive labels
which differ at least two. Also an -coloring of is any labeling of
the vertices of such that any two adjacent vertices receive labels which
differ at least two and any two vertices with distance two receive distinct
labels. Assume that a partial -labeling is given in a graph . A
general question is whether can be extended to a -labeling of .
We show that the extension is feasible if and only if a Hamiltonian path
consistent with some distance constraints exists in the complement of . Then
we consider line graph of bipartite multigraphs and determine the minimum
number of labels in -coloring and -labeling of these graphs.
In fact we obtain easily computable formulas for the path covering number and
the maximum path of the complement of these graphs. We obtain a polynomial time
algorithm which generates all Hamiltonian paths in the related graphs. A
special case is the Cartesian product graph and the generation of
-squares.Comment: 20 pages, 7 figures, accepted pape
First-Fit coloring of Cartesian product graphs and its defining sets
Get PDFLet the vertices of a Cartesian product graph be ordered by an
ordering . By the First-Fit coloring of we mean the
vertex coloring procedure which scans the vertices according to the ordering
and for each vertex assigns the smallest available color. Let
be the number of colors used in this coloring. By
introducing the concept of descent we obtain a sufficient condition to
determine whether , where and
are arbitrary orders. We study and obtain some bounds for , where is any quasi-lexicographic ordering. The First-Fit
coloring of does not always yield an optimum coloring. A
greedy defining set of is a subset of vertices in the
graph together with a suitable pre-coloring of such that by fixing the
colors of the First-Fit coloring of yields an optimum
coloring. We show that the First-Fit coloring and greedy defining sets of
with respect to any quasi-lexicographic ordering (including the known
lexicographic order) are all the same. We obtain upper and lower bounds for the
smallest cardinality of a greedy defining set in , including some
extremal results for Latin squares.Comment: Accepted for publication in Contributions to Discrete Mathematic
Results on the Grundy chromatic number of graphs
No full textAbstractGiven a graph G, by a Grundy k-coloring of G we mean any proper k-vertex coloring of G such that for each two colors i and j, i<j, every vertex of G colored by j has a neighbor with color i. The maximum k for which there exists a Grundy k-coloring is denoted by Γ(G) and called Grundy (chromatic) number of G. We first discuss the fixed-parameter complexity of determining Γ(G)⩾k, for any fixed integer k and show that it is a polynomial time problem. But in general, Grundy number is an NP-complete problem. We show that it is NP-complete even for the complement of bipartite graphs and describe the Grundy number of these graphs in terms of the minimum edge dominating number of their complements. Next we obtain some additive Nordhaus–Gaddum-type inequalities concerning Γ(G) and Γ(Gc), for a few family of graphs. We introduce well-colored graphs, which are graphs G for which applying every greedy coloring results in a coloring of G with χ(G) colors. Equivalently G is well colored if Γ(G)=χ(G). We prove that the recognition problem of well-colored graphs is a coNP-complete problem
A new vertex coloring heuristic and corresponding chromatic number
Get PDFOne method to obtain a proper vertex coloring of graphs using a reasonable
number of colors is to start from any arbitrary proper coloring and then repeat
some local re-coloring techniques to reduce the number of color classes. The
Grundy (First-Fit) coloring and color-dominating colorings of graphs are two
well-known such techniques. The color-dominating colorings are also known and
commonly referred as {\rm b}-colorings. But these two topics have been studied
separately in graph theory. We introduce a new coloring procedure which
combines the strategies of these two techniques and satisfies an additional
property. We first prove that the vertices of every graph can be
effectively colored using color classes say such that
for any two colors and with , any vertex of color
is adjacent to a vertex of color , there exists a set of vertices of such that for any and is adjacent to for each with
, and for each and with , the vertex
has a neighbor in . This provides a new vertex coloring heuristic which
improves both Grundy and color-dominating colorings. Denote by the
maximum number of colors used in any proper vertex coloring satisfying the
above properties. The quantifies the worst-case behavior of the
heuristic. We prove the existence of such that but for each .
For each positive integer we construct a family of finitely many colored
graphs satisfying the property that if for a
graph then contains an element from as a colored
subgraph. This provides an algorithmic method for proving numeric upper bounds
for
On irreversible spread of influence in edge-weighted graphs
Get PDFVarious kinds of spread of influence occur in real world social and virtual networks. These phenomena are formulated by activation processes and irreversible dynamic monopolies in combinatorial graphs representing the topology of the networks. In most cases, the nature of influence is weighted and the spread of influence depends on the weight of edges. The ordinary formulation and results for dynamic monopolies do not work for such models. In this paper we present a graph theoretical analysis for spread of weighted influence and mention a real world example realizing the activation model with weighted influence. Then we obtain some extremal bounds and algorithmic results for activation process and dynamic monopolies in directed and undirected graphs with weighted edges
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
More algorithmic results for problems of spread of influence in edge-weighted graphs with and without incentives: More algorithmic results for problems of spread of influence
No full textMany phenomena in real-world social networks are interpreted as the spread of influence between activated and non-activated elements within the network. These phenomena are formulated by combinatorial graphs, where vertices represent the elements and edges represent social ties between elements. A main problem is to study important subsets of elements (target sets or dynamic monopolies) such that their activation spreads to the entire network. In edge-weighted networks, the influence between two adjacent vertices depends on the weight of their edge. In models with incentives, the main problem is to minimize the total amount of incentives (called optimal target vectors) that can be offered to vertices such that some vertices are activated and their activation spreads to the whole network. Algorithmic study of target sets and vectors is a hot research field. We prove an inapproximability result for optimal target sets in edge-weighted networks, even for complete graphs. Some other hardness and polynomial time results are presented for optimal target vectors and degenerate threshold assignments in edge-weighted networks. Lastly, we obtain a hardness result for target sets in edge-weighted tournaments
Bounds for the Grundy chromatic number of graphs in terms of domination number
Get PDFFor any graph , the Grundy (or First-Fit) chromatic number of , denoted
by (also ), is defined as the maximum number
of colors used by the First-Fit (greedy) coloring of the vertices of .
Determining the Grundy number is -complete, and obtaining bounds for
in terms of the known graph parameters is an active research topic.
By a star partition of we mean any partition of into say such that each contains a vertex adjacent to any other
vertex in . In this paper using the star partition of graphs we obtain the
first upper bounds for the Grundy number in terms of the domination number. We
also prove some bounds in terms of the domination number and girth of graphs.Comment: 16 pages, 5 figures, accepted for publication in Bolletin of the
Belgian Mathematical Societ
- …
