Page 1 Next

Displaying 1 – 20 of 90

Showing per page

The 3-path-step operator on trees and unicyclic graphs

Bohdan Zelinka (2002)

Mathematica Bohemica

E. Prisner in his book Graph Dynamics defines the k -path-step operator on the class of finite graphs. The k -path-step operator (for a positive integer k ) is the operator S k ' which to every finite graph G assigns the graph S k ' ( G ) which has the same vertex set as G and in which two vertices are adjacent if and only if there exists a path of length k in G connecting them. In the paper the trees and the unicyclic graphs fixed in the operator S 3 ' are studied.

The 3-Rainbow Index of a Graph

Lily Chen, Xueliang Li, Kang Yang, Yan Zhao (2015)

Discussiones Mathematicae Graph Theory

Let G be a nontrivial connected graph with an edge-coloring c : E(G) → {1, 2, . . . , q}, q ∈ ℕ, where adjacent edges may be colored the same. A tree T in G is a rainbow tree if no two edges of T receive the same color. For a vertex subset S ⊆ V (G), a tree that connects S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for each k-subset S of V (G) is called the k-rainbow index of G, denoted by rxk(G). In this paper,...

The classification of edges and the change in multiplicity of an eigenvalue of a real symmetric matrix resulting from the change in an edge value

Kenji Toyonaga, Charles R. Johnson (2017)

Special Matrices

We take as given a real symmetric matrix A, whose graph is a tree T, and the eigenvalues of A, with their multiplicities. Each edge of T may then be classified in one of four categories, based upon the change in multiplicity of a particular eigenvalue, when the edge is removed (i.e. the corresponding entry of A is replaced by 0).We show a necessary and suficient condition for each possible classification of an edge. A special relationship is observed among 2-Parter edges, Parter edges and singly...

The color-balanced spanning tree problem

Štefan Berežný, Vladimír Lacko (2005)

Kybernetika

Suppose a graph G = ( V , E ) whose edges are partitioned into p disjoint categories (colors) is given. In the color-balanced spanning tree problem a spanning tree is looked for that minimizes the variability in the number of edges from different categories. We show that polynomiality of this problem depends on the number p of categories and present some polynomial algorithm.

The cubic mapping graph for the ring of Gaussian integers modulo n

Yangjiang Wei, Jizhu Nan, Gaohua Tang (2011)

Czechoslovak Mathematical Journal

The article studies the cubic mapping graph Γ ( n ) of n [ i ] , the ring of Gaussian integers modulo n . For each positive integer n > 1 , the number of fixed points and the in-degree of the elements 1 ¯ and 0 ¯ in Γ ( n ) are found. Moreover, complete characterizations in terms of n are given in which Γ 2 ( n ) is semiregular, where Γ 2 ( n ) is induced by all the zero-divisors of n [ i ] .

The Dynamics of the Forest Graph Operator

Suresh Dara, S.M. Hegde, Venkateshwarlu Deva, S.B. Rao, Thomas Zaslavsky (2016)

Discussiones Mathematicae Graph Theory

In 1966, Cummins introduced the “tree graph”: the tree graph T(G) of a graph G (possibly infinite) has all its spanning trees as vertices, and distinct such trees correspond to adjacent vertices if they differ in just one edge, i.e., two spanning trees T1 and T2 are adjacent if T2 = T1 − e + f for some edges e ∈ T1 and f ∉ T1. The tree graph of a connected graph need not be connected. To obviate this difficulty we define the “forest graph”: let G be a labeled graph of order α, finite or infinite,...

The fundamental constituents of iteration digraphs of finite commutative rings

Jizhu Nan, Yangjiang Wei, Gaohua Tang (2014)

Czechoslovak Mathematical Journal

For a finite commutative ring R and a positive integer k 2 , we construct an iteration digraph G ( R , k ) whose vertex set is R and for which there is a directed edge from a R to b R if b = a k . Let R = R 1 ... R s , where s > 1 and R i is a finite commutative local ring for i { 1 , ... , s } . Let N be a subset of { R 1 , , R s } (it is possible that N is the empty set ). We define the fundamental constituents G N * ( R , k ) of G ( R , k ) induced by the vertices which are of the form { ( a 1 , , a s ) R : a i D ( R i ) if R i N , otherwise a i U ( R i ) , i = 1 , ... , s } , where U ( R ) denotes the unit group of R and D ( R ) denotes the zero-divisor set of R . We investigate...

The leafage of a chordal graph

In-Jen Lin, Terry A. McKee, Douglas B. West (1998)

Discussiones Mathematicae Graph Theory

The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - 1/2 lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use asteroidal...

The lifted root number conjecture for fields of prime degree over the rationals: an approach via trees and Euler systems

Cornelius Greither, Radiu Kučera (2002)

Annales de l’institut Fourier

The so-called Lifted Root Number Conjecture is a strengthening of Chinburg’s Ω ( 3 ) - conjecture for Galois extensions K / F of number fields. It is certainly more difficult than the Ω ( 3 ) -localization. Following the lead of Ritter and Weiss, we prove the Lifted Root Number Conjecture for the case that F = and the degree of K / F is an odd prime, with another small restriction on ramification. The very explicit calculations with cyclotomic units use trees and some classical combinatorics for bookkeeping. An important...

Currently displaying 1 – 20 of 90

Page 1 Next