Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs

Tjaša Paj; Simon Špacapan

The search session has expired. Please query the service again.

Displaying similar documents to “Maximum Independent Sets in Direct Products of Cycles or Trees with Arbitrary Graphs”

The Crossing Numbers of Products of Path with Graphs of Order Six

Marián Klešč, Jana Petrillová (2013)

Discussiones Mathematicae Graph Theory

Similarity:

The crossing numbers of Cartesian products of paths, cycles or stars with all graphs of order at most four are known. For the path Pn of length n, the crossing numbers of Cartesian products G⃞Pn for all connected graphs G on five vertices are also known. In this paper, the crossing numbers of Cartesian products G⃞Pn for graphs G of order six are studied. Let H denote the unique tree of order six with two vertices of degree three. The main contribution is that the crossing number of the...

The Wiener, Eccentric Connectivity and Zagreb Indices of the Hierarchical Product of Graphs

Hossein-Zadeh, S., Hamzeh, A., Ashrafi, A. (2012)

Serdica Journal of Computing

Similarity:

Let G1 = (V1, E1) and G2 = (V2, E2) be two graphs having a distinguished or root vertex, labeled 0. The hierarchical product G2 ⊓ G1 of G2 and G1 is a graph with vertex set V2 × V1. Two vertices y2y1 and x2x1 are adjacent if and only if y1x1 ∈ E1 and y2 = x2; or y2x2 ∈ E2 and y1 = x1 = 0. In this paper, the Wiener, eccentric connectivity and Zagreb indices of this new operation of graphs are computed. As an application, these topological indices for a class of alkanes are computed. ACM...

On path-quasar Ramsey numbers

Binlong Li, Bo Ning (2015)

Annales UMCS, Mathematica

Similarity:

Let G1 and G2 be two given graphs. The Ramsey number R(G1,G2) is the least integer r such that for every graph G on r vertices, either G contains a G1 or Ḡ contains a G2. Parsons gave a recursive formula to determine the values of R(Pn,K1,m), where Pn is a path on n vertices and K1,m is a star on m+1 vertices. In this note, we study the Ramsey numbers R(Pn,K1,m), where Pn is a linear forest on m vertices. We determine the exact values of R(Pn,K1∨Fm) for the cases m ≤ n and m ≥ 2n, and...

The Estrada Index

Hanyuan Deng, Slavko Radenković, Ivan Gutman (2009)

Zbornik Radova

Similarity:

The Estrada Index: An Updated Survey

Ivan Gutman, Hanyuan Deng, Slavko Radenković (2011)

Zbornik Radova

Similarity:

New bounds for the broadcast domination number of a graph

Richard Brewster, Christina Mynhardt, Laura Teshima (2013)

Open Mathematics

Similarity:

A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σv∈V f(v), and the broadcast number λ b (G) is the minimum cost of a dominating broadcast. A set X ⊆ V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly...

On the basis number of the composition of different ladders with some graphs.

Alzoubi, Maref Y., Jaradat, M.M.M. (2005)

International Journal of Mathematics and Mathematical Sciences

Similarity:

Inequalities between distance-based graph polynomials

I. Gutman, Olga Miljković, B. Zhou, M. Petrović (2006)

Bulletin, Classe des Sciences Mathématiques et Naturelles, Sciences mathématiques

Similarity:

On $(δ, χ)$ -bounded families of graphs.

Gyárfás, András, Zaker, Manouchehr (2011)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

The evolution of uniform random planar graphs.

Dowden, Chris (2010)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

The number of labelled $k$ -arch graphs.

Lamathe, Cédric (2004)

Journal of Integer Sequences [electronic only]

Similarity:

The Well-Covered Dimension Of Products Of Graphs

Isaac Birnbaum, Megan Kuneli, Robyn McDonald, Katherine Urabe, Oscar Vega (2014)

Discussiones Mathematicae Graph Theory

Similarity:

We discuss how to find the well-covered dimension of a graph that is the Cartesian product of paths, cycles, complete graphs, and other simple graphs. Also, a bound for the well-covered dimension of Kn × G is found, provided that G has a largest greedy independent decomposition of length c < n. Formulae to find the well-covered dimension of graphs obtained by vertex blowups on a known graph, and to the lexicographic product of two known graphs are also given.