Wyniki wyszukiwania

1

On eulerian irregularity in graphs

100%

Andrews E., Lumduanhom C., Zhang P.

Discussiones Mathematicae Graph Theory

|

2014

|

tom 34

|

nr 2

391-408

EN

A closed walk in a connected graph G that contains every edge of G exactly once is an Eulerian circuit. A graph is Eulerian if it contains an Eulerian circuit. It is well known that a connected graph G is Eulerian if and only if every vertex of G is even. An Eulerian walk in a connected graph G is a closed walk that contains every edge of G at least once, while an irregular Eulerian walk in G is an Eulerian walk that encounters no two edges of G the same number of times. The minimum length of an irregular Eulerian walk in G is called the Eulerian irregularity of G and is denoted by EI(G). It is known that if G is a nontrivial connected graph of size m, then [...] . A necessary and sufficient condition has been established for all pairs k,m of positive integers for which there is a nontrivial connected graph G of size m with EI(G) = k. A subgraph F in a graph G is an even subgraph of G if every vertex of F is even. We present a formula for the Eulerian irregularity of a graph in terms of the size of certain even subgraph of the graph. Furthermore, Eulerian irregularities are determined for all graphs of cycle rank 2 and all complete bipartite graphs

2

On Monochromatic Subgraphs of Edge-Colored Complete Graphs

88%

Andrews E., Fujie F., Kolasinski K., Lumduanhom C., Yusko A.

Discussiones Mathematicae Graph Theory

|

2014

|

tom 34

|

nr 1

5-22

EN

In a red-blue coloring of a nonempty graph, every edge is colored red or blue. If the resulting edge-colored graph contains a nonempty subgraph G without isolated vertices every edge of which is colored the same, then G is said to be monochromatic. For two nonempty graphs G and H without isolated vertices, the mono- chromatic Ramsey number mr(G,H) of G and H is the minimum integer n such that every red-blue coloring of Kn results in a monochromatic G or a monochromatic H. Thus, the standard Ramsey number of G and H is bounded below by mr(G,H). The monochromatic Ramsey numbers of graphs belonging to some common classes of graphs are studied. We also investigate another concept closely related to the standard Ram- sey numbers and monochromatic Ramsey numbers of graphs. For a fixed integer n ≥ 3, consider a nonempty subgraph G of order at most n con- taining no isolated vertices. Then G is a common monochromatic subgraph of Kn if every red-blue coloring of Kn results in a monochromatic copy of G. Furthermore, G is a maximal common monochromatic subgraph of Kn if G is a common monochromatic subgraph of Kn that is not a proper sub- graph of any common monochromatic subgraph of Kn. Let S(n) and S*(n) be the sets of common monochromatic subgraphs and maximal common monochromatic subgraphs of Kn, respectively. Thus, G ∈ S(n) if and only if R(G,G) = mr(G,G) ≤ n. We determine the sets S(n) and S*(n) for 3 ≤ n ≤ 8.

3

On Twin Edge Colorings of Graphs

88%

Andrews E., Helenius L., Johnston D., VerWys J., Zhang P.

Discussiones Mathematicae Graph Theory

|

2014

|

tom 34

|

nr 3

613-627

EN

A twin edge k-coloring of a graph G is a proper edge coloring of G with the elements of Zk so that the induced vertex coloring in which the color of a vertex v in G is the sum (in Zk) of the colors of the edges incident with v is a proper vertex coloring. The minimum k for which G has a twin edge k-coloring is called the twin chromatic index of G. Among the results presented are formulas for the twin chromatic index of each complete graph and each complete bipartite graph

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

3 Andrews E.

2 Lumduanhom C.

2 Zhang P.

1 Fujie F.

1 Helenius L.

1 Johnston D.

1 Kolasinski K.

1 VerWys J.

1 Yusko A.

3 2014

On eulerian irregularity in graphs

On Monochromatic Subgraphs of Edge-Colored Complete Graphs

On Twin Edge Colorings of Graphs