Displaying 501 – 520 of 908

Showing per page

On stratification and domination in graphs

Ralucca Gera, Ping Zhang (2006)

Discussiones Mathematicae Graph Theory

A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let F be a 2-stratified graph rooted at some blue vertex v. An F-coloring of a graph is a red-blue coloring of the vertices of G in which every blue vertex v belongs to a copy of F rooted at v. The F-domination number γ F ( G ) is the minimum number of red vertices in an F-coloring of G. In...

On strong digraphs with a prescribed ultracenter

Gary Chartrand, Heather Gavlas, Kelly Schultz, Steven J. Winters (1997)

Czechoslovak Mathematical Journal

The (directed) distance from a vertex u to a vertex v in a strong digraph D is the length of a shortest u - v (directed) path in D . The eccentricity of a vertex v of D is the distance from v to a vertex furthest from v in D . The radius rad D is the minimum eccentricity among the vertices of D and the diameter diam D is the maximum eccentricity. A central vertex is a vertex with eccentricity r a d D and the subdigraph induced by the central vertices is the center C ( D ) . For a central vertex v in a strong digraph...

On strongly regular graphs with m2 = qm3 and m3 = qm2

Lepovic, Mirko (2011)

Serdica Mathematical Journal

2010 Mathematics Subject Classification: 05C50.We say that a regular graph G of order n and degree r і 1 (which is not the complete graph) is strongly regular if there exist non-negative integers t and q such that |SiЗSj| = t for any two adjacent vertices i and j, and |SiЗSj| = q for any two distinct non-adjacent vertices i and j, where Sk denotes the neighborhood of the vertex k. Let l1 = r, l2 and l3 be the distinct eigenvalues of a connected strongly regular graph. Let m1 = 1, m2 and m3 denote...

On subalgebra lattices of a finite unary algebra. I.

Konrad Pióro (2001)

Mathematica Bohemica

One of the main aims of the present and the next part [15] is to show that the theory of graphs (its language and results) can be very useful in algebraic investigations. We characterize, in terms of isomorphisms of some digraphs, all pairs 𝐀 , 𝐋 , where 𝐀 is a finite unary algebra and L a finite lattice such that the subalgebra lattice of 𝐀 is isomorphic to 𝐋 . Moreover, we find necessary and sufficient conditions for two arbitrary finite unary algebras to have isomorphic subalgebra lattices. We solve...

On subalgebra lattices of a finite unary algebra. II.

Konrad Pióro (2001)

Mathematica Bohemica

We use graph-algebraic results proved in [8] and some results of the graph theory to characterize all pairs 𝐋 1 , 𝐋 2 of lattices for which there is a finite partial unary algebra such that its weak and strong subalgebra lattices are isomorphic to 𝐋 1 and 𝐋 2 , respectively. Next, we describe other pairs of subalgebra lattices (weak and relative, etc.) of a finite unary algebra. Finally, necessary and sufficient conditions are found for quadruples 𝐋 1 , 𝐋 2 , 𝐋 3 , 𝐋 4 of lattices for which there is a finite unary algebra having...

On subgraphs without large components

Glenn G. Chappell, John Gimbel (2017)

Mathematica Bohemica

We consider, for a positive integer k , induced subgraphs in which each component has order at most k . Such a subgraph is said to be k -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a k -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for 2 -coloring...

On Super (a, d)-H-Antimagic Total Covering of Star Related Graphs

K.M. Kathiresan, S. David Laurence (2015)

Discussiones Mathematicae Graph Theory

Let G = (V (G),E(G)) be a simple graph and H be a subgraph of G. G admits an H-covering, if every edge in E(G) belongs to at least one subgraph of G that is isomorphic to H. An (a, d)-H-antimagic total labeling of G is a bijection λ: V (G) ∪ E(G) → {1, 2, 3, . . . , |V (G)| + |E(G)|} such that for all subgraphs H′ isomorphic to H, the H′ weights [...] constitute an arithmetic progression a, a+d, a+2d, . . . , a+(n−1)d where a and d are positive integers and n is the number of subgraphs of G isomorphic...

On super (a,d)-edge antimagic total labeling of certain families of graphs

P. Roushini Leely Pushpam, A. Saibulla (2012)

Discussiones Mathematicae Graph Theory

A (p, q)-graph G is (a,d)-edge antimagic total if there exists a bijection f: V(G) ∪ E(G) → {1, 2,...,p + q} such that the edge weights Λ(uv) = f(u) + f(uv) + f(v), uv ∈ E(G) form an arithmetic progression with first term a and common difference d. It is said to be a super (a, d)-edge antimagic total if the vertex labels are {1, 2,..., p} and the edge labels are {p + 1, p + 2,...,p + q}. In this paper, we study the super (a,d)-edge antimagic total labeling of special classes of graphs derived from...

Currently displaying 501 – 520 of 908